1. When plants colonize new habitats, the novel interactions they form with new mutualists or enemies can immediately affect plant performance. These novel interactions also may provoke rapid evolutionary responses and can be ideal scenarios for investigating how species interactions influence plant evolution. 2. To explore how mutualists influence the evolution of colonizing plant populations, we capitalized on an experiment in which two former agricultural fields were seeded with identical prairie seed mixes in 2010. Six years later, we compared how populations of the legume Chamaecrista fasciculata from these sites and their original (shared) source population responded to nitrogen-fixing rhizobia from the restoration sites in a greenhouse reciprocal cross-inoculation experiment. 3. We found that the two populations differed both from their original source population and from each other in the benefits they derive from rhizobia, that one population has evolved reduced allocation to rhizobia (i.e., forms fewer rhizobium-housing nodules). 4. Synthesis. Our results suggest that these plant populations have evolved different ways of interacting with rhizobia, potentially in response to differences in rhizobium quality between sites. Our study illustrates how microbial mutualists may shape plant evolution in new environments and highlights how variation in microbial mutualists potentially may select for different evolutionary strategies in plant hosts.