The increase of the world’s population and the decrease of arable land due to abiotic stresses, especially salinity and heavy metals, are causing growing concerns over agricultural sustainability. The application of Plant Growth-Promoting Rhizobacteria (PGPR) is considered as a useful tool to reverse such environmental stressors. The aim of the study is to investigate the growth-promoting effects of a recently identified Algerian Sahara rhizobacterium Pseudomonas plecoglossicida strain Pp20 (Pp20) in the interaction with Zea mays cv DZ. This study also aims to assess the capacity of Pp20 to alleviate damages on maize roots caused by salt and aluminum. Our results revealed that this PGPR strain is producing the enzyme ACC deaminase, degrading the plant hormone ethylene precursor 1-aminocyclopropane-1-carboxylic acid (ACC). In addition, it produces and secretes small amounts of the plant growth-promoting hormone indole-3-acetic acid (IAA). Under greenhouse conditions, the inoculation with the PGPR induced growth stimulatory effects. Inoculation showed improvements on all of the growth parameters, particularly root fresh and dry biomass (increases up to 114% and 121%, respectively). The plant’s better performance was indicated also by increases in photosynthesis-associated parameters as chlorophyll and carbohydrate contents. Improvements of the root growth by PGPRs have been observed in the presence of 150 mM NaCl reaching up to 70% more in the length of the seminal roots and 270% increase in the number of lateral roots. In the presence of 90 µM AlCl₃, the root growth parameters due to the bacterial inoculants are even better. Increases in lengths of seminal roots and root dry mass by 231% and 93%, respectively, were found. Furthermore, we could show that Pp20 itself exhibited tolerance to high NaCl and AlCl₃ concentrations. Overall, these results highlight the potential of this new PGPR in the phytostimulation and the induction of abiotic stress resistance in economically relevant crop plant.