Fifty-eight new isolates were obtained from root nodules of common bean (Phaseolus vulgaris) cultivated in soils originating from different agroecological areas in Senegal and Gambia (West Africa). A polyphasic approach including both phenotypic and genotypic techniques was used to study the diversity of the 58 Rhizobium isolates and to determine their taxonomic relationships with reference strains. All the techniques performed, analysis of multilocus enzyme electrophoretic patterns, SDS-PAGE profiles of total cell proteins, PCR-RFLP analysis of the genes encoding 16S rRNA and of the 16S-23S RNA intergenic spacer region (ITS-PCR-RFLP), auxanographic tests using API galleries and nodulation tests lead to the consensus conclusion that the new rhizobial isolates formed two main distinct groups, I and II, belonging to Rhizobium tropici type B and Rhizobium etli, respectively. By MLEE R. etli and group II strains showed several related electrophoretic types, evidencing some extent of internal heterogeneity among them. This heterogeneity was confirmed by other techniques (ITS-PCR-RFLP, SDS-PAGE and host-plant-specificity) with the same nine distinct strains of group II showing some differences from the core of group II (54 strains).