The genus Bradyrhizobium encompasses a variety of bacteria that can live in symbiotic and endophytic associations with legumes and non-legumes, and are characterized by physiological and symbiotic versatility and broad geographical distribution. However, despite indications of great genetic variability within the genus, only eight species have been described, mainly because of the highly conserved nature of the 16S rRNA gene. In this study, 169 strains isolated from 43 different legumes were analysed by rep-PCR with the BOX primer, by sequence analysis of the 16S rRNA gene and the 16S–23S rRNA intergenic transcribed spacer (ITS) and by multilocus sequence analysis (MLSA) of four housekeeping genes, glnII, recA, atpD and dnaK. Considering a cut-off at a level of 70 % similarity, 80 rep-PCR profiles were distinguished, which, together with type strains, were clustered at a very low level of similarity (24 %). In both single and concatenated analyses of the 16S rRNA gene and ITS sequences, two large groups were formed, with bootstrap support of 99 % in the concatenated analysis. The first group included the type and/or reference strains of Bradyrhizobium japonicum, B. betae, B. liaoningense, B. canariense and B. yuanmingense and B. japonicum USDA 110, and the second group included strains related to Bradyrhizobium elkanii USDA 76T, B. pachyrhizi PAC48T and B. jicamae PAC68T. Similar results were obtained with MLSA of glnII, recA, atpD and dnaK. Greatest variability was observed when the atpD gene was amplified, and five strains related to B. elkanii revealed a level of variability never reported before. Another important observation was that a group composed of strains USDA 110, SEMIA 5080 and SEMIA 6059, all isolated from soybean, clustered in all six trees with high bootstrap support and were quite distinct from the clusters that included B. japonicum USDA 6T. The results confirm that MLSA is a rapid and reliable way of providing information on phylogenetic relationships and of identifying rhizobial strains potentially representative of novel species.