From a total of 80 bacterial strains isolated from root nodules of Lupinus angustifolius grown wild in the North-Eastern Algerian region of El Tarf, 64 plant host-nodulating strains clustered into 17 random amplified polymorphic DNA (RAPD) fingerprinting groups. The nearly complete 16S rRNA gene sequence from the representative strain of each group revealed they were closely related to members of the genus Bradyrhizobium of the Alphaproteobacteria, but their affiliation at the species level was not clear. Sequencing of the housekeeping genes glnII and recA, and their concatenated phylogenetic analysis, showed that 12 strains belong to B. lupini, other 2 strains affiliated with B. diazoefficiens and that 1 strain was closely related to B. japonicum. The remaining two strains showed similarity values ≤95% with B. cytisi and could represent new lineages within the genus Bradyrhizobium. Sequencing of the symbiotic nodC gene from 4 selected bradyrhizobial strains showed they were all similar to those of the species included in symbiovar genistearum.