The long-term maintenance of specialized mutualisms remains an evolutionary puzzle. Recent focus has been on factors governing the stability of these mutualisms, including sanctions by the host, partner choice, and coevolutionary constraint, that is, the genetic correlation (rG) between fitness of both partners. So far these studies have been typically carried out in a single environment. Here, we ask if the genetic correlation between fitness of the host plant Medicago truncatula (Fabaceae) and its bacterial symbiont Sinorhizobium meliloti is affected by the presence/absence of a monoterpene (carvacrol) leached into the soil by Thymus vulgaris—a common plant of the Mediterranean vegetation, often co-occuring with Medicago. We show that the presence of carvacrol in the soil dramatically affects fitness of the rhizobial partner and increases the magnitude of rG between plant and rhizobia fitness (rG= 0.02 ± 0.05 vs. rG= 0.57 ± 0.02). This finding emphasizes the importance of heterogeneity in the biotic environment for understanding the evolution of species interactions.