The diversity of rhizobia associated with introduced and native Acacia species in Algeria was investigated from soil samples collected across seven districts distributed in arid and semi-arid zones. The in vitro tolerances of rhizobial strains to NaCl and high temperature in pure culture varied greatly regardless of their geographical and host plant origins but were not correlated with the corresponding edaphoclimatic characteristics of the sampling sites, as clearly demonstrated by principal component analysis. Based on 16S rRNA gene sequence comparisons, the 48 new strains isolated were ranked into 10 phylogenetic groups representing five bacterial genera, namely, Ensifer, Mesorhizobium, Rhizobium, Bradyrhizobium, and Ochrobactrum. Acacia saligna, an introduced species, appeared as the most promiscuous host because it was efficiently nodulated with the widest diversity of rhizobia taxa including both fast-growing ones, Rhizobium, Ensifer, and Mesorhizobium, and slow-growing Bradyrhizobium. The five other Acacia species studied were associated with fast-growing bacterial taxa exclusively. No difference in efficiency was found between bacterial taxa isolated from a given Acacia species. The tolerances of strains to salinity and temperature remains to be tested in symbiosis with their host plants to select the most adapted Acacia sp.-LNB taxa associations for further revegetation programs.