Fluorescent Pseudomonas are ubiquitous soil bacteria that usually establish mutualistic associations with plants, promoting their growth and health by several mechanisms. This makes them interesting candidates for the development of crop bio-inoculants. In this work, we isolated phosphate-solubilizing fluorescent Pseudomonas from the rhizosphere and inner tissues of different plant species growing in red soil from Misiones, Argentina. Seven isolates displaying strong phosphate solubilization were selected for further studies. Molecular identification by rpoD genotyping indicated that they belong to different species within the P. fluorescens and P. putida phylogenetic groups. Screening for in vitro traits such as phosphate solubilization, growth regulators synthesis or degradation, motility and antagonism against phytopathogens or other bacteria, revealed a unique profile of characteristics for each strain. Their plant growth-promoting potential was assayed using lettuce as a model for inoculation under controlled and greenhouse conditions. Five of the strains increased the growth of lettuce plants. Overall, the strongest lettuce growth promoter under both conditions was strain ZME4, isolated from inner tissues of maize. No clear association between lettuce growth promotion and in vitro beneficial traits was detected. In conclusion, several phosphate solubilizing pseudomonads from red soil were isolated that display a rich array of plant growth promotion traits, thus showing a potential for the development of new inoculants.