The diversity and phylogeny of root-nodule bacteria isolated from common bean grown in Mozambique and different provinces of South Africa was studied by restriction fragment length polymorphism (RFLP) and phylogenetic analysis. The combined restriction banding pattern of 16S rRNA and nifH profile-generated dendrogram grouped all test isolates into four major clusters with XXI restriction groups and three clusters with VIII restriction groups. Location-based clustering was observed with the 16S rRNA RFLP analysis. Phylogenetic analysis of 16S rRNA, glnII, gyrB and gltA sequences showed that common bean was nodulated specifically by Rhizobium etli in Mozambican soils, and by a diverse group of Rhizobium species in South African soils (e.g. R. etli, R. phaseoli, R. sophoriradicis, R. leucaenae and novel group of Rhizobium spp.). Isolates from the Eastern Cape region of South Africa were dominated by R. leucaenae. Overall, the results suggested high nodulation promiscuity of common bean grown in Southern Africa. The nifH and nodC sequence analysis classified all the test isolates with R. etli group, except for isolates TUTPVSA117, TUTPVSA114 and TUTPVSA110 which delineated with R. tropici group. This finding was inconsistent with the phylogram of the housekeeping genes, and is probably an indication of horizontal gene transfer among the Rhizobium isolates tested.