Mutualists may play an important role in invasion success. The ability to take advantage of novel mutualists or survive and reproduce despite a lack of mutualists may facilitate invasion by those individuals with such traits. Here, we used two greenhouse studies to examine how soil microbial communities in general and mutualistic rhizobia in particular affect the performance of a legume species (Medicago polymorpha) that has invaded five continents. We performed two plant growth experiments with Medicago polymorpha, inoculating them with soil slurries in one experiment or rhizobial cultures in another experiment. For both experiments, we compared the growth of Medicago in competition with conspecific or heterospecific plants and examined variation among plant genotypes collected from the native and introduced ranges. We found that all genotypes experienced similar increases in biomass and formed more nodules that house rhizobia bacteria when inoculated with soil from a previously invaded site, compared to uninoculated plants or plants inoculated with soil from uninvaded and low invasion sites. In a second experiment, plants inoculated with rhizobia generally produced more biomass, had greater tolerance to interspecific competition, and had greater effects on competitor biomass than uninoculated plants. However, plant genotypes collected from the native range benefited more from rhizobia and were less tolerant of competition relative to genotypes collected from the introduced range. In the introduced range, compatible mutualists may not be readily available but competition is intense, causing Medicago to evolve to benefit less from interactions with rhizobia mutualists, while simultaneously becoming more tolerant of competition.