Previous studies have shown that the sugarcane microbiome harbors diverse plant growth promoting (PGP) microorganisms, including nitrogen-fixing bacteria, and the objective of this study was to design a genome-enabled approach to prioritize sugarcane associated nitrogen-fixing bacteria according to their potential as biofertilizers. Using a systematic high throughput approach, 22 pure cultures of nitrogen-fixing bacteria were isolated and tested for diazotrophic potential by PCR amplification of nitrogenase (nifH) genes, common molecular markers for nitrogen fixation capacity. Genome sequencing confirmed the presence of intact nitrogenase nifH genes and operons in the genomes of 18 of the isolates. Isolate genomes also encoded operons for phosphate solubilization, siderophore production operons, and other PGP phenotypes. Klebsiella pneumoniae strains comprised 14 of the 22 nitrogen-fixing isolates, and four others were members of closely related genera to Klebsiella. A computational phenotyping approach was developed to rapidly screen for strains that have high potential for nitrogen fixation and other PGP phenotypes while showing low risk for virulence and antibiotic resistance. The majority of sugarcane isolates were below a genotypic and phenotypic threshold, showing uniformly low predicted virulence and antibiotic resistance compared to clinical isolates. Six prioritized strains were experimentally evaluated for PGP phenotypes: nitrogen fixation, phosphate solubilization, and the production of siderophores, gibberellic acid and indole acetic acid. Results from the biochemical assays were consistent with the computational phenotype predictions for these isolates. Our results indicate that computational phenotyping is a promising tool for the assessment of benefits and risks associated with bacteria commonly detected in agricultural ecosystems.