A total of 274 bacterial strains were isolated from the root nodules of Prosopis juliflora, growing in two arid soils of the eastern area of Morocco. A physiological plate screening allowed the selection of 15 strains that could tolerate NaCl concentrations between 175 and 500 mM. These were compared with 15 strains chosen from among the ones which did not tolerate high salinity. The diversity of strains was first assessed by rep-PCR amplification fingerprinting using BOXA1R and ERIC primers. An analysis of the PCR-amplified 16S rDNA gene digestion profiles using five endonucleases indicated the presence of different lineages among the taxa associated with P. juliflora nodules in the soils studied. Nucleotide sequencing of the small subunit rRNA gene and BLAST analysis showed that P. juliflora could host at least six bacterial species in this region and that the identity of those associated with high salt tolerance was clearly distinct from that of the salt-sensitive ones. Among the former, the first type displayed 99% similarity with different members of the genus Sinorhizobium, the second 97% similarity with species within the genus Rhizobium, while the third ribosomal type had 100% homology to Achromobacter xylosoxidans. Within the salt-sensitive isolates the prevailing type observed showed 98% similarity with Rhizobium multihospitium and R. tropici, a second type had 98% similarity to R. giardinii, and a further case displayed 97% colinearity with the Ensifer group including E. maghrebium and E. xericitae. All of the thirty strains encompassing these types re-nodulated P. juliflora in microbiologically controlled conditions and all of them were shown to possess a copy of the nodC gene. This is the first report detecting the betaproteobacterial genus Achromobacter as nodule-forming species for legumes. The observed variability in symbiont species and the abundance of nodulation-proficient strains is in line with the observation that the plant always appears to be nodulated and efficiently fixing nitrogen in spite of a wide range of soil and environmental conditions.