The nature and direction of coevolutionary interactions between species is expected to differentiate among distinct environments. Consequently, locally coevolved symbiotic traits would be well matched in similar environments, but mismatched elsewhere. In a classic mutualistic tradeoff, rhizobia provide nitrogen (N) to legume host plants in return for photosynthates. Despite earlier predictions, there is little evidence so far that spatial differences in soil N content mediate the coevolutionary outcome of the legume–Rhizobium mutualism. To test the existence of such selection mosaics, different genotypes of Vicia cracca and Rhizobium leguminosarum originating from spatially and environmentally highly differentiated sites were cross inoculated across different soil N regimes. In accordance with theoretical predictions, we found highly significant effects of genotype by genotype by environment (G× G × E) interactions, on both nodulation and plant growth, even when R. leguminosarum genotypes showed high genetic similarity. Our results show that the trajectory of the coevolutionary interactions between rhizobia and legumes is differentiated across different environments, and that selection mosaics may play an important role in shaping differences in the genetic composition of rhizobial populations.