Halotolerant plant-growth-promoting rhizobacteria (PGPR) could not only promote plant growth, but also help in counteracting the detrimental effects of salt stress. In the present study, a total of 76 bacteria were isolated from the rhizosphere, non-rhizospheric soil and endophytes of the halophyte Salsola tetrandra, collected from natural saline soils in Algeria. Phylogenetic analysis based on the 16S rDNA sequence of Gram-negative bacteria (n = 51) identified, showed seventeen representative isolates grouped into four genera (Pseudomonas, Acinetobacter, Enterobacter, and Providencia). These bacterial isolates that exhibited different PGPR traits were selected and tested for their ability to tolerate different abiotic stress (NaCl, PEG8000, and pH). The majority of isolates were drought tolerant (60% of PEG8000) and had an optimal growth at high pH values (pH 9 and 11) and some strains tolerated 2 M of NaCl. Strains identified as Enterobacter xiangfangensis BE1, Providencia rettgeri BR5 and Pseudomonas stutzeri MLR6 showed high capacity of adaptation on their PGP traits. The salt-tolerant isolates were finally chosen to promote growth and enhance salt tolerance, separately or combined, of Arabidopsis thaliana (Col-0) exposed or not to 0.1 M NaCl, by following fresh and root weight, primary root elongation and lateral root number. The best bacterial effect was recorded for the MLR6 strain in increasing shoot fresh weight and for BE1 in terms of root fresh weight in the absence of salt stress. At stressed conditions, all growth parameters declined. However, inoculation of Arabidopsis thaliana with the three bacterial strains (MLR6, BE1 and BR5), single or in co-culture, conferred an increase in the shoot weight, primary root length and lateral root number. The use of these strains separately or combined as biofertilizers seems to be a powerful tool in the development of sustainable agriculture in saline soils.