(1) Background: Increasing salinity, further potentiated by climate change and soil degradation, will jeopardize food security even more. Therefore, there is an urgent need for sustainable agricultural practices capable of maintaining high crop yields despite adverse conditions. Here, we tested if wheat, a salt-sensitive crop, could be a good reservoir for halotolerant bacteria with plant growth-promoting (PGP) capabilities. (2) Methods: We used two agricultural soils from Algeria, which differ in salinity but are both used to grow wheat. Soil halotolerant bacterial strains were isolated and screened for 12 PGP traits related to phytohormone production, improved nitrogen and phosphorus availability, nutrient cycling, and plant defence. The four \u2018most promising\u2019 halotolerant PGPB strains were tested hydroponically on wheat by measuring their effect on germination, survival, and biomass along a salinity gradient. (3) Results: Two halotolerant bacterial strains with PGP traits were isolated from the non-saline soil and were identified as Bacillus subtilis and Pseudomonas fluorescens, and another two halotolerant bacterial strains with PGP traits were isolated from the saline soil and identified as B. megaterium. When grown under 250 mM of NaCl, only the inoculated wheat seedlings survived. The halotolerant bacterial strain that displayed all 12 PGP traits and promoted seed germination and plant growth the most was one of the B. megaterium strains isolated from the saline soil. Although they both belonged to the B. megaterium clade and displayed a remarkable halotolerance, the two bacterial strains isolated from the saline soil differed in two PGP traits and had different effects on plant performance, which clearly shows that PGP potential is not phylogenetically determined. (4) Conclusions: Our data highlight that salt-sensitive plants and non-saline soils can be reservoirs for halotolerant microbes with the potential to become effective and sustainable strategies to improve plant tolerance to salinity. However, these strains need to be tested under field conditions and with more crops before being considered biofertilizer candidates.