Abstract The diversity and phylogeny of 32 rhizobial strains isolated from nodules of common bean plants grown on 30 sites in Ethiopia were examined using AFLP fingerprinting and MLSA. Based on cluster analysis of AFLP fingerprints, test strains were grouped into six genomic clusters and six single positions. In a tree built from concatenated sequences of recA, glnII, rpoB and partial 16S rRNA genes, the strains were distributed into seven monophyletic groups. The strains in the groups B, D, E, G1 and G2 could be classified as Rhizobium phaseoli, R. etli, R. giardinii, Agrobacterium tumefaciens complex and A. radiobacter, respectively, whereas the strains in group C appeared to represent a novel species. R. phaseoli, R. etli, and the novel group were the major bean nodulating rhizobia in Ethiopia. The strains in group A were linked to R. leguminosarum species lineages but not resolved. Based on recA, rpoB and 16S rRNA genes sequences analysis, a single test strain was assigned as R. leucaenae. In the nodC tree the strains belonging to the major nodulating groups were clustered into two closely linked clades. They also had almost identical nifH gene sequences. The phylogenies of nodC and nifH genes of the strains belonging to R. leguminosarum, R. phaseoli, R. etli and the putative new species (collectively called R. leguminosarum species complex) were not consistent with the housekeeping genes, suggesting symbiotic genes have a common origin which is different from the core genome of the species and indicative of horizontal gene transfer among these rhizobia.