Sixty-seven isolates were isolated from nodules collected on roots of Mediterranean shrubby legumes Retama raetam and Retama sphaerocarpa growing in seven ecological-climatic areas of northeastern Algeria. Genetic diversity of the Retama isolates was analyzed based on genotyping by restriction fragment length polymorphism of PCR-amplified fragments of the 16S rRNA gene, the intergenic spacer (IGS) region between the 16S and 23S rRNA genes (IGS), and the symbiotic genes nifH and nodC. Eleven haplotypes assigned to the Bradyrhizobium genus were identified. Significant biogeographical differentiation of the rhizobial populations was found, but one haplotype was predominant and conserved across the sites. All isolates were able to cross-nodulate the two Retama species. Accordingly, no significant genetic differentiation of the rhizobial populations was found in relation to the host species of origin. Sequence analysis of the 16S rRNA gene grouped the isolates with Bradyrhizobium elkanii, but sequence analyses of IGS, the housekeeping genes (dnaK, glnII, recA), nifH, and nodC yielded convergent results showing that the Retama nodule isolates from the northeast of Algeria formed a single evolutionary lineage, which was well differentiated from the currently named species or well-delineated unnamed genospecies of bradyrhizobia. Therefore, this study showed that the Retama species native to northeastern Algeria were associated with a specific clade of bradyrhizobia. The Retama isolates formed three sub-groups based on IGS and housekeeping gene phylogenies, which might form three sister species within a novel bradyrhizobial clade