Plant growth promoting (PGP) bacteria are known to enhance plant growth and protect them from environmental stresses through different pathways. The rhizosphere of perennial plants, including olive, may represent a relevant reservoir of PGP bacteria. Here, seven bacterial strains isolated from olive rhizosphere have been characterized taxonomically by 16S sequencing and biochemically, to evaluate their PGP potential. Most strains were identified as Pseudomonas or Bacillus spp., while the most promising ones belonged to genera Pseudomonas and Curtobacterium. Those strains have been tested for their capacity to grow under osmotic or salinity stress and to improve the germination and early development of Triticum durum subjected or not to those stresses. The selected strains had the ability to grow under severe stress, and a positive effect has been observed in non-stressed seedlings inoculated with one of the Pseudomonas strains, which showed promising characteristics that should be further evaluated. The biochemical and taxonomical characterization of bacterial strains isolated from different niches and the evaluation of their interaction with plants under varying conditions will help to increase our knowledge on PGP microorganisms and their use in agriculture.