Limited solubility of the Tanzania’s Minjingu phosphate rock (MPR) in non-acidic soil conditions has held back its potential for widespread use in agricultural production. This study was designed to isolate, characterize and test phosphate-solubilizing bacteria for their potential to increase solubility of MPR and enhance maize plant growth under field conditions. Ten out of 19 isolates showing greatest phosphate solubilization indices on a Pikovskaya agar medium were further characterized for other plant-growth promoting traits including production of IAA, siderophores and ammonia. Two of them, namely isolates-MdE4 and MdG1 substantially outperformed other isolates in phosphate solubilization and production of IAA, ammonia and siderophores. The two isolates molecularly identified as Klebsiella variicola-MdE4 and K. variicola-MdG1 produced up 701, 699 and 750, 680 μg/ml of soluble phosphate from tricalcium phosphate and hard Minjungu rock phosphate, respectively. Additionally, Biorock P- a biofertilizer formulation containing MdE4 and MdG1 co-cultured in a molasses-based modified broth medium retained most of the phosphate solubilizing potential and other plant-growth promoting traits of MdE4 and MdG1. Co-application of MdE1 and MdG1-containing “bio-rock P” and inorganic phosphate at 20 kg P/ha resulted in higher maize grain yield than that of positive control (40 kg P/ha) under field conditions. The two isolates- Klebsiella variicola-MdE4 and K. variicola-MdG1 have the potential for use in a biofertilizer formulation for commercial field applications.