Distribution and diversity of rhizobial strains associated with Acacia senegal (L.) Willd. in relation to seed provenances in soils from arid (Dahra) and semiarid (Goudiry) zones of Senegal were investigated. PCR-RFLP performed on 16S-23S rDNA intergenic spacer (IGS) of nodule crude extracts revealed a high genetic diversity of rhizobial strains, which was higher in the semiarid region than in the arid region. The distribution of rhizobial populations was influenced by soil physical and chemical characteristics, and by A. senegal provenances as shown by the analysis of correspondence. In contrast, the phenotypic diversity of rhizobial strains was not correlated with the soil origin. The phylogenetic tree (performed by the maximum likelihood algorithm) of IGS 16S-23S sequences showed that most of the rhizobial strains nodulating A. senegal were closely related to Mesorhizobium plurifarium. Our results showed that rhizobial taxa associated with A. senegal were mainly distributed according to soil physical and chemical characteristics, and A. senegal provenances. A large subset of A. senegal root-nodulating bacteria had high diversity that correlated with the most favourable environmental conditions. Understanding the diversity and distribution of rhizobial strains may be exploited in the formulation of A. senegal inoculants for different seed provenances for resilience to soil stresses in various environmental conditions.