Mutualistic bacteria infect most eukaryotic species in nearly every biome. Nonetheless, two dilemmas remain unresolved about bacterial-eukaryote mutualisms: how do mutualist phenotypes originate in bacterial lineages and to what degree do mutualists traits drive or hinder bacterial diversification? Here, we reconstructed the phylogeny of the hyperdiverse phylum Proteobacteria to investigate the origins and evolutionary diversification of mutualistic bacterial phenotypes. Our ancestral state reconstructions (ASRs) inferred a range of 34-39 independent origins of mutualist phenotypes in Proteobacteria, revealing the surprising frequency with which host-beneficial traits have evolved in this phylum. We found proteobacterial mutualists to be more often derived from parasitic than from free-living ancestors, consistent with the untested paradigm that bacterial mutualists most often evolve from pathogens. Strikingly, we inferred that mutualists exhibit a negative net diversification rate (speciation minus extinction), which suggests that mutualism evolves primarily via transitions from other states rather than diversification within mutualist taxa. Moreover, our ASRs infer that proteobacterial mutualist lineages exhibit a paucity of reversals to parasitism or to free-living status. This evolutionary conservatism of mutualism is contrary to long-standing theory, which predicts that selection should often favour mutants in microbial mutualist populations that exploit or abandon more slowly evolving eukaryotic hosts. © 2013 The Author(s) Published by the Royal Society. All rights reserved.