This study focused on the genetic, symbiotic and phenotypic diversity of a collection of 12 Vachellia seyal and Prosopis juliflora rhizobial strains that were isolated from soils influenced by the roots of the grass Sporobolus robustus. Phylogenetic trees were constructed based on data from the 16S rRNA gene, from a multi-locus sequence analysis (MLSA) of the housekeeping genes recA, atpD, glnA and gyrB, as well as from the symbiotic genes nodA, nodC and nifH. Most of the mesorhizobial strains were clustered with the M. plurifarium type strain ORS 1032T and the 16S rRNA gene was as discriminatory as the other housekeeping genes. The Ensifer collection was closely related to E. alkalisoli YIC 4027T and E. fredii LMG 6217T using 16S rRNA and MLSA. Amplification of the Rhizobium collection was only observed with the 16S rRNA gene, where the strains were clustered with Rhizobium sp. 1B, Rhizobium sp. SEMIA 6411, Rhizobium sp. AS1-101a and Rhizobium sp. ORS 3441. The phylogeny of the nifH gene from Mesorhizobium and Ensifer strains were similar to those of nodulation genes (nodA and nodC). The nodA-nodC and nifH gene phylogenies were not consistent with those of 16S rRNA and the housekeeping genes. Ensifer genospecies tolerated high salinity better than the other genotypes after testing on a salt content gradient up to 49‰. We conclude that the rhizosphere of Sporobolus tussocks harbors a rhizobial microbiota, which could be capable of helping V. seyal and P. juliflora to grow better in saline soils.