Fifty-eight rhizobial strains were isolated from root nodules of Vicia faba cv. Equina and Vicia faba cv. Minor by the host-trapping method in soils collected from eleven sites in Bejaia, Eastern Algeria. Eleven genotypic groups were distinguished based on the combined PCR/RFLP of 16S rRNA, 16S-23S rRNA intergenic spacer and symbiotic (nodC and nodD-F) genes and further confirmed by multilocus sequence analysis (MLSA) of three housekeeping genes (recA, atpD and rpoB), the 16S rRNA gene and the nodulation genes nodC and nodD. Of the 11 genotypes, 5 were dominant and 2 were the most represented. Most of the strains shared high nodD gene sequence similarity with Rhizobium leguminosarum sv. viciae; their nodC sequences were similar to both Rhizobium leguminosarum and Rhizobium laguerreae. Sequence analyses of the 16S-23S rRNA intergenic spacer showed that all the new strains were phylogenetically related to those described from Vicia sativa and V. faba in several African, European, American and Asian countries, with which they form a group related to Rhizobium leguminosarum. Phylogenetic analysis based on MLSA of 16S rRNA, recA, atpD and rpoB genes allowed the affiliations of strain AM11R to Rhizobium leguminosarum sv. viciae and of strains EB1 and ES8 to Rhizobium laguerreae. In addition, two separate clades with <97% similarity may represent two novel genospecies within the genus Rhizobium.