The interaction between legumes and rhizobia has been well studied in the context of a mutualistic, nitrogen-fixing symbiosis. The fitness of legumes, including important agricultural crops, is enhanced by the plants' ability to develop symbiotic associations with certain soil bacteria that fix atmospheric nitrogen into a utilizable form, namely, ammonia, via a chemical reaction that only bacteria and archaea can perform. Of the bacteria, members of the alpha subclass of the protebacteria are the best-known nitrogen-fixing symbionts of legumes. Recently, members of the beta subclass of the proteobacteria that induce nitrogen-fixing nodules on legume roots in a species-specific manner have been identified. In this issue, Bontemps et al. reveal that not only are these newly identified rhizobia novel in shifting the paradigm of our understanding of legume symbiosis, but also, based on symbiotic gene phylogenies, have a history that is both ancient and stable. Expanding our understanding of novel plant growth promoting rhizobia will be a valuable resource for incorporating alternative strategies of nitrogen fixation for enhancing plant growth.