A longstanding paradigm predicts that microbial parasites and mutualists exhibit disparate evolutionary patterns. Parasites are predicted to promote arms races with hosts, rapid evolution and sexual recombination. By contrast, mutualists have been linked with beneficial coadaptation, evolutionary stasis and asexuality. In this review we discuss the recent surge of molecular data on microbes that are being used to test and reshape these ideas. New analyses reveal that beneficial microbes often share mechanisms of infection and defense with parasites, and can also exhibit rapid evolution and extensive genetic exchange. To explain these patterns, new paradigms must take into account the varied population biology of beneficial microbes, their potential conflicts with hosts, and the mosaic nature of genome evolution that requires locus-based tests to analyze the genetics of host adaptation.