The capacity of beneficial microbes to compete for host infection-and the ability of hosts to discriminate among them-introduces evolutionary conflict that is predicted to destabilize mutualism. We investigated fitness outcomes in associations between legumes and their symbiotic rhizobia to characterize fitness impacts of microbial competition. Diverse Bradyrhizobium strains varying in their capacity to fix nitrogen symbiotically with a common host plant, Acmispon strigosus, were tested in full-factorial coinoculation experiments involving 28 pairwise strain combinations. We analyzed the effects of interstrain competition and host discrimination on symbiotic-interaction outcomes by relativizing fitness proxies to clonally infected and uninfected controls. More than one thousand root nodules of coinoculated plants were genotyped to quantify strain occupancy, and the Bradyrhizobium strain genome sequences were analyzed to uncover the genetic bases of interstrain competition outcomes. Strikingly, interstrain competition favored a fast-growing, minimally beneficial rhizobia strain. Host benefits were significantly diminished in coinoculation treatments relative to expectations from clonally inoculated controls, consistent with competitive interference among rhizobia that reduced both nodulation and plant growth. Competition traits appear polygenic, linked with inter-strain allelopathic interactions in the rhizosphere. This study confirms that competition among strains can destabilize mutualism by favoring microbes that are superior in colonizing host tissues but provide minimal benefits to host plants. Moreover, our findings help resolve the paradox that despite efficient host control post infection, legumes nonetheless encounter rhizobia that vary in their nitrogen fixation.