Human induced environmental change may require rapid adaptation of plant populations and crops, but the genomic basis of environmental adaptation remain poorly understood. We analysed polymorphic loci from the perennial crop Medicago sativa (alfalfa or lucerne) and the annual legume model species M. truncatula to search for a common set of candidate genes that might contribute to adaptation to abiotic stress in both annual and perennial Medicago species. We identified a set of candidate genes of adaptation associated with environmental gradients along the distribution of the two Medicago species. Candidate genes for each species were detected in homologous genomic linkage blocks using genome-environment (GEA) and genome-phenotype association analyses. Hundreds of GEA candidate genes were species-specific, of these, 13.4% (M. sativa) and 24% (M. truncatula) were also significantly associated with phenotypic traits. A set of 168 GEA candidates were shared by both species, which was 25.4% more than expected by chance. When combined, they explained a high proportion of variance for certain phenotypic traits associated with adaptation. Genes with highly conserved functions dominated among the shared candidates and were enriched in gene ontology terms that have shown to play a central role in drought avoidance and tolerance mechanisms by means of cellular shape modifications and other functions associated with cell homeostasis. Our results point to the existence of a molecular basis of adaptation to abiotic stress in Medicago determined by highly conserved genes and gene functions. We discuss these results in light of the recently proposed omnigenic model of complex traits.