Acacia senegal and Acacia seyal are small, deciduous legume trees, most highly valued for nitrogen fixation and for the production of gum arabic, a commodity of international trade since ancient times. Symbiotic nitrogen fixation by legumes represents the main natural input of atmospheric N2 into ecosystems which may ultimately benefit all organisms. We analyzed the nod and nif symbiotic genes and symbiotic properties of root-nodulating bacteria isolated from A. senegal and A. seyal in Senegal. The symbiotic genes of rhizobial strains from the two Acacia species were closed to those of Mesorhizobium plurifarium and grouped separately in the phylogenetic trees. Phylogeny of rhizobial nitrogen fixation gene nifH was similar to those of nodulation genes (nodA and nodC). All A. senegal rhizobial strains showed identical nodA, nodC, and nifH gene sequences. By contrast, A. seyal rhizobial strains exhibited different symbiotic gene sequences. Efficiency tests demonstrated that inoculation of both Acacia species significantly affected nodulation, total dry weight, acetylene reduction activity (ARA), and specific acetylene reduction activity (SARA) of plants. However, these cross-inoculation tests did not show any specificity of Mesorhizobium strains toward a given Acacia host species in terms of infectivity and efficiency as stated by principal component analysis (PCA). This study demonstrates that large-scale inoculation of A. senegal and A. seyal in the framework of reafforestation programs requires a preliminary step of rhizobial strain selection for both Acacia species.