Phosphate-solubilizing bacteria (PSB) increase phosphate bioavailability, thereby reducing the application frequency of chemical fertilizers in the production of Nicotiana tabacum (tobacco). In this study, PSB were isolated from tobacco plants for the first time. These PSB were screened in vitro for their ability to solubilize inorganic P (Pi) when grown in association with tobacco plants. Thirty-six PSB with the ability to solubilize P_i were isolated and screened for their indolyl-3-acetic acid and siderophore-producing capabilities. In addition, all 36 PSB strains had a partial fragment of their 16S rRNA gene sequenced. The analysis revealed high sequence identity to 16S rDNA sequences from Bacillus, Arthrobacter, Providencia, Enterobacter, Proteus, Psychrobacter, Serratia, Rhodococcus, Pseudomonas, Ochrobactrum, and Acinetobacter. Of the 36 PSB strains analyzed, three (Psychrobacter alimentarius HB15, Enterobacter ludwigii HB21, and Ochrobactrum haematophilum HB36) were selected for a controlled plant inoculation experiment. Inoculation of tobacco plants with these bacterial strains significantly increased plant dry weight. Additionally, inoculation increased P, K, and N uptake by tobacco seedlings as well as soil P availability. The increases observed with inoculation were even more pronounced when tricalcium phosphate (TCP) was added to the soil. The phosphate-solubilizing activity of these three strains was correlated with the release of gluconic, tartaric, acetic, and citric organic acids. Overall, co-inoculation of PSB and TCP appears to represent a promising option for increasing the yield of tobacco plants. The adoption of this technique could provide a pathway to reducing fertilizer input in agricultural settings.