The genetic structure of rhizobia nodulating pea and lentil in Algeria, Northern Africa was determined. A total of 237 isolates were obtained from root nodules collected on lentil (Lens culinaris), proteaginous and forage pea (Pisum sativum) growing in two eco-climatic zones, sub-humid and semi-arid, in Eastern Algeria. They were characterised by PCR-restriction fragment length polymorphism (RFLP) of the 16S-23S rRNA intergenic region (IGS), and the nodD-F symbiotic region. The combination of these haplotypes allowed the isolates to be clustered into 26 distinct genotypes, and all isolates were classified as Rhizobium leguminosarum. Symbiotic marker variation (nodD-F) was low but with the predominance of one nod haplotype (g), which had been recovered previously at a high frequency in Europe. Sequence analysis of the IGS further confirmed its high variability in the studied strains. An AMOVA analysis showed highly significant differentiation in the IGS haplotype distribution between populations from both eco-climatic zones. This differentiation was reflected by differences in dominant genotype frequencies. Conversely, no host plant effect was detected. The nodD gene sequence-based phylogeny suggested that symbiotic gene diversity in pea and lentil nodulating rhizobial populations in Algeria was low compared to that reported elsewhere in the world.