The mutualism between legumes and nitrogen-fixing bacteria (rhizobia) is a key feature of many ecological and agricultural systems, particularly because of the resulting enrichment of soil nitrogen. While many aspects of this interaction are well characterized, little is known about the effects of the legume-rhizobia mutualism on other organisms, particularly herbivores. We investigated the effects of different rhizobial sources on the abundance of a specialized legume herbivore, the soybean aphid (Aphis glycines). Soybean (Glycine max) associating with indigenous rhizobia strains supported reduced aphid populations compared to plants inoculated with a commercial rhizobial preparation or given nitrogen fertilizer. Plant size, total leaf nitrogen content, and the general intensity of nodulation were similar in both rhizobia-associated treatments, suggesting that these plant attributes cannot explain the observed differences in aphid abundance. Genetic analyses confirmed that the commercial rhizobia strains were distinct from indigenous strains. Our results suggest that plant-rhizobia interactions can influence plant’s resistance to herbivores and that particular rhizobia strains can confer greater resistance to their mutualist partners than others. Understanding the implications of these differences is potentially important, as legume plants often encounter a variety of rhizobia strains in the surrounding soil, including both naturally occurring bacteria and strains introduced by agricultural inoculations. Utilization of strains that confer greater resistance to the host plant might reduce pesticide needs in legume cultivation.