Rhizobia are phylogenetically disparate α- and β-proteobacteria that have achieved the environmentally essential function of fixing atmospheric nitrogen (N2) in symbiosis with legumes. All rhizobia elicit the formation of root – or occasionally stem – nodules, plant organs dedicated to the fixation and assimilation of nitrogen. Bacterial colonization of these nodules culminates in a remarkable case of sustained intracellular infection in plants. Rhizobial phylogenetic diversity raised the question of whether these soil bacteria shared a common core of symbiotic genes. In this article, we review the cumulative evidence from recent genomic and genetic analyses pointing toward an unexpected variety of mechanisms that lead to symbiosis with legumes.