Bacteria that establish nitrogen-fixing symbiosis in specialized plant structures belong to only three of over 100 bacterial phyla. Among these, rhizobial symbioses are the best known and nodulation genes (nod) have been described in many species. nodA phylogenies revealed a larger diversity in Bradyrhizobium than in other genera and suggest that bradyrhizobial nod genes are the oldest in agreement to the proposal that nod genes evolved in Bradyrhizobium (Plant Soil 161:11-20, 1994). In many cases, rhizobial symbiotic and housekeeping genes have different evolutionary histories in relation to the lateral transfer of symbiotic genes among bacteria. Misclassified Rhizobium strains were identified, to properly identify rhizobial species we propose the use of fragments of the rpoB and dnaK genes, which according to probability analyses reflect the behavior of whole genes. With these analyses several rhizobial species related to Agrobacterium tumefaciens may be reclassified to a genus other than Rhizobium. © 2010 Springer-Verlag Berlin Heidelberg.