Aims: To assess the phenotypic, symbiotic and genotypic diversity scope of Mesorhizobium spp. strains associated with Acacia seyal (Del.) isolated from different agro-ecological zones in Senegal, and uses of susceptible microbial inoculum in a reafforestation process. Methods and Results: A polyphasic approach including phenotypic and genotypic techniques was used to study the diversity and their relationships with other biovars and species of rhizobia. The geographical origins of the strains have limited effect on their phylogenetic and phenotypic classification. Nodulation tests indicated promiscuity of the strains studied, because they were capable of nodulating six woody legume species (Acacia auriculiformis, Acacia senegal, A. seyal, Acacia tortilis ssp. raddiana, Leucaena leucocephala and Prosopis juliflora). Sequencing and phylogenetic analyses of nodA, nodC and nifH genes pointed out that in contrast to nodA gene, the phylogenies of nodC and nifH genes were not consistent with that of 16S rRNA, indicating that these genes of the A. seyal-nodulating rhizobia might have different origins. Microbial inoculation on nonsterile soil had significant effect on the nodules number and the growth of the seedlings, indicating that these strains of rhizobia might be used as inoculum. Conclusions: The results indicated that A. seyal is a nonselective host that can establish effective symbiosis with Mesorhizobium spp. strains from diverse genomic backgrounds and that the selected A. seyal-nodulating rhizobia could enhance plant growth. Significance and Impact of the Study: These results showed the important role that A. seyal could play in the improvement of reafforestation process as a promiscuous host, which can establish effective symbiosis with rhizobia from diverse genomic backgrounds.