Two diametric paradigms have been proposed to model the molecular co-evolution of microbial mutualists and their eukaryotic hosts. In one, mutualist and host exhibit an antagonistic arms race and each partner evolves rapidly to maximize their own fitness from the interaction at potential expense of the other. In the opposing model, conflicts between mutualist and host are largely resolved and the interaction is characterized by evolutionary stasis. We tested these opposing frameworks in two lineages of mutualistic rhizobia, Sinorhizobium fredii and Bradyrhizobium japonicum. To examine genes demonstrably important for host-interactions we coupled the mining of genome sequences to a comprehensive functional screen for type III effector genes, which are necessary for many Gram-negative pathogens to infect their hosts. We demonstrate that the rhizobial type III effector genes exhibit a surprisingly high degree of conservation in content and sequence that is in contrast to those of a well characterized plant pathogenic species. This type III effector gene conservation is particularly striking in the context of the relatively high genome-wide diversity of rhizobia. The evolution of rhizobial type III effectors is inconsistent with the molecular arms race paradigm. Instead, our results reveal that these loci are relatively static in rhizobial lineages and suggest that fitness conflicts between rhizobia mutualists and their host plants have been largely resolved.