Fifty-two slow-growing strains were isolated from root nodules of Calicotome spinosa grown in the Northeast of Algeria and grouped in 24 rep-PCR clusters. One representative strain for each profile was further phylogenetically characterized. The nearly complete 16S rRNA gene sequence indicated that all strains were affiliated to Bradyrhizobium. Multi-Locus Sequence Analysis (MLSA) of the atpD, glnII and recA genes and of the 16S-23S rRNA internal transcribed spacer (ITS) showed that these strains formed four divergent clusters: one close to Bradyrhizobium canariense and Bradyrhizobium lupini and three others separate from all the described species, representing three putative new Bradyrhizobium species. A phylogenetic analysis based on the nodC gene sequence affiliated the strains to either of the two symbiovars, genistearum or retamae.