Salinity is a major detrimental factor for plant growth and crop productivity that could be alleviated by the use of plant growth promoting bacteria (PGPB) with a protective role in such stressful conditions. In this study, four native strains of the genus Pseudomonas were isolated from both a strongly saline soil and the rhizosphere of soybean plants grown in a slightly saline soil. These isolates were able to tolerate high NaCl concentration, showed efficient adhesion to biotic and abiotic surfaces and efficiently colonized the rhizosphere of soybean grown in slightly saline soil. In these conditions, the four strains outperformed Pseudomonas putida KT2440, a strain known as a good root colonizer of different plants. Inoculation with all the isolates improved seed germination and vigor index, particularly in saline conditions, and one of them also had a positive effect on shoot length and phenological state of soybean plants grown in slightly saline soil. Our results suggest that the search for classical plant growth promotion traits may not be mandatory for selecting putative PGPB. Instead, characteristics such as stress tolerance, adhesion, competitive colonization, and plant growth promotion should be tested using the soil types and crops in which the bacteria will be used.