The application of plant growth promoting bacteria (PGPB) with biocontrol activities as inoculants of crop plants against phytopathogenic fungi and insect pests provide a biological alternative to the use of agrochemicals. Two Pseudomonas protegens strains were isolated from agricultural well water in a heavy metal contaminated area near Bejaia, northeastern Algeria. The isolates S4LiBe and S5LiBe had 16S rRNA gene sequence similarities of 99.4%–99.7% with P. protegens CHA0T and other P. protegens strains. The phenotypic profiles tested with BIOLOG-GN2-microplates showed differences in 12 of 95 carbon sources tested, as compared to the type strain P. protegens CHA0T. The isolates S4LiBe and S5LiBe showed plant growth promoting potential which is commonly associated with the production of the phytohormone indole acetic acid and siderophores and the solubilization of insoluble phosphate. In addition, they produce chitinase and other polymer degrading enzymes. As the strains S4LiBe and S5LiBe were isolated from heavy metal polluted well water, they are resistant against several heavy metals (2.0 mM K2Cr2O7 and 3.0 mM CoSO4, HgSO4, CdSO4 8H2O and PbCl2), while the reference strain P. protegens CHA0T was very sensitive to Hg2+ and Cd2+ and had lower tolerance towards Co2+ and Pb2+. The isolates S4LiBe and S5LiBe were active in mycelial growth inhibition assays against Botrytis cinerea, Verticillium dahliae, Fusarium graminearum, Aspergillus niger and Aspergillus flavus (growth inhibition between 88% and 48%). Furthermore, S4LiBe and S5LiBe showed effective insecticidal activities, when tested in the Galleria injection assay and they were tested positive for the insect toxin gene fitD alike the reference strain CHA0T. Finally, inoculation of barley seeds with S5LiBe in non-polluted agricultural soil significantly stimulated the germination rate and growth of seedlings, with increased shoot length (11.96 cm ± 0.59), shoot and root fresh weight (0.10 g ± 0.009, 0.04 g ± 0.006), shoot and root dry weight (0.075 g ± 0.003, 0.03 g ± 0.007) as compared to non-inoculated plants (10.23 cm ± 0.84, 0.06 g ± 0.007, 0.025 g ± 0.006, 0.047 g ± 0.006, and 0.016 g ± 0.004, respectively). In heavy metal contaminated soil, inoculation with strain S5LiBe resulted in similar increase of germination rate and growth parameters of barley like in the non-polluted soil, while P. protegens CHA0T inoculated plants were not stimulated. Thus, the heavy metal tolerant isolates S4LiBe and S5LiBe have a potential as beneficial bacteria for agricultural application even in heavy metal polluted soils, e.g. for the stimulation of biomass crops. The demonstration of successful isolation from agricultural well water may open more ready access for a wide variety of this kind of beneficial bacteria for agricultural application.