Phosphorus (P) deficiency limits the growth, development, and productivity of rice. To better understand the underlying mechanisms in P-deficiency tolerance and the role of Pup1 QTL in enhancing P use efficiency (PUE) for the development of P-efficient rice cultivars, a pair of contrasting rice genotypes (Pusa-44 and NIL-23) was applied to investigate the morpho-physio-biochemical and proteomic variation under P-starvation stress. The rice genotypes were grown hydroponically in a PusaRich medium with adequate P (16 mg/kg, +P) or without P (0 mg/kg, -P) for 30 d. P-starvation manifested a significant reductions in root and shoot biomass, shoot length, leaf area, total chlorophyll, and P, nitrogen and starch contents, as well as protein kinase activity. The stress increased root-to-shoot biomass ratio, root length, sucrose content, and acid phosphatase activity, particularly in the P-tolerant genotype (NIL-23). Comparative proteome analysis revealed several P metabolism-associated proteins (including OsCDPKs, OsMAPKs, OsCPKs, OsLecRK2, and OsSAPks) to be expressed in the shoot of NIL-23, indicating that multiple protein kinases were involved in P-starvation/deficiency tolerance. Moreover, the up-regulated expression of OsrbcL, OsABCG32, OsSUS5, OsPolI-like B, and ClpC2 proteins in the shoot, and OsACA9, OsACA8, OsSPS2F, OsPP2C15, and OsBiP3 in the root of NIL-23, indicated their role in P-starvation stress control through the Pup1 QTL. Thus, our findings indicated that -P stress-responsive proteins, in conjunction with morpho-physio-biochemical modulations, improved PUE and made NIL-23 a P-deficiency tolerant genotype due to the introgression of the Pup1 QTL in the Pusa-44 background.