The low phosphorus use efficiency (PUE) and the high P fertilizer cost are reasons why it is necessary to find sustainable phosphorus (P) sources for sesame, in which bacteria are potential candidates. The aim of this study was to determine a level of the applied P fertilizer and P-solubilizing rhizosphere bacteria (PSRB) for the maximum growth and yield of sesame. A two-factor experiment was conducted in a completely randomized block design. The first factor (i) was the P fertilizer rate, including 0%, 50%, 75%, and 100% P of the recommended fertilizer rate (RFR); the other was (ii) the supplementation of the PSRB, including no supplemented bacteria, a single strain of Enterobacter asburiae ASD-56, ASD-15, or ASD-43, and the mixture of all the three strains, with five replications. The results revealed that fertilizing with 100% P of the RFR enhanced means of the plant height (5.4 cm), the number of capsules (4.4 capsules plant−1), the total P uptake (34.3 mg P pot−1), and the sesame seed yield (16.4 g pot−1) in comparison with the case with no P fertilizer. The supplementation of the E. asburiae ASD-56, ASD-15, and ASD-43 improved values of the soluble P in soil, the total P uptake in plants, and the seed yield at 82.6 mg P kg−1, 73.1 mg P pot−1, and 15.2 g pot−1, respectively, compared with 72.2 mg P kg−1, 45.5 mg P pot−1, and 10.6 g pot−1 in treatment with no supplemented bacteria. Individually or aggregately applying the three E. asburiae ASD-56, ASD-15, and ASD-43 strains not only reduced the average amount of the P fertilizer used by 25–50% P of the RFR but also increased the P uptake in plants by 8.50–36.9% and the average sesame seed yield by 2.94–58.7%, in comparison with those in the treatment fertilized with 100% P of the RFR. The mixture of the PSRB contributed to reducing 50% of the RFR, and increasing the yield by 43.4%.