The Peruvian Andean Plateau, one of the main production areas of native varieties of Chenopodium quinoa, is exposed to abrupt decreases in environmental temperature, affecting crop production. Plant-growth-promoting rhizobacteria that tolerate low temperatures could be used as organic biofertilizers in this region. We aimed to bioprospect the native psychrotolerant bacteria of the quinoa rhizosphere in this region that show plant-growth-promoting traits. Fifty-one strains belonging to the quinoa rhizosphere were characterised; 73% of the total could grow at low temperatures (4, 6, and 15 °C), whose genetic diversity based on DNA amplification of interspersed repetitive elements (BOX) showed 12 different profiles. According to the 16S rRNA sequence, bacterial species belonging to the classes Beta- and Gammaproteobacteria were identified. Only three (6%) isolates identified as nonpathogenic bacteria exhibited plant-growth-promoting activities, like IAA production, phosphate solubilization, growth in a nitrogen-free medium, and ACC deaminase production at 6 and 15 °C. ILQ215 (Pseudomonas silesiensis) and JUQ307 (Pseudomonas plecoglossicida) strains showed significantly positive plant growth effects in aerial length (about 50%), radicular length (112% and 79%, respectively), and aerial and radicular mass (above 170% and 210%, respectively) of quinoa plants compared with the control without bacteria. These results indicate the potential of both psychrotolerant strains to be used as potential organic biofertilizers for quinoa in this region.