Bottom-up evolutionary approaches, including geographically-explicit population genomic analyses, have the power to reveal the mechanistic basis of adaptation. Here we conduct a population genomic analysis in the model legume, Medicago truncatula, in order to characterize population genetic structure and identify symbiosis-related genes showing evidence of spatially-variable selection. Using RAD-seq, we generated over 26,000 SNPs from 191 accessions from within three regions of the native range in Europe. Results from STRUCTURE analysis identify 5 distinct genetic clusters with divisions that separate east and west regions in the Mediterranean basin. Much of the genetic variation is maintained within sampling sites, and there is evidence for isolation by distance. Extensive linkage disequilibrium was identified, particularly within populations. We conducted genetic outlier analysis with FST-based genome scans and a bayesian modeling approach (PCAdapt). There were 70 core outlier loci shared between these distinct methods with one clear candidate symbiosis related gene, DMI1. This work sets that stage for functional experiments to determine the important phenotypes that selection has acted upon and complementary efforts in rhizobium populations.