The microalgal species Chlorella vulgaris was cultivated in batch conditions to identify the optimum set of initial conditions for the best biomass growth rate, phosphate removal, polyphosphate accumulation, and protein productivity. To study the effect of phosphorus deficiency caused stress, the microalgal biomass was exposed to phosphorus deficiency conditions for periods varying between 1 and 10 days and inoculated at different initial biomass and phosphate concentrations. A 10-day period of phosphate deficiency, supported by low initial biomass concentration (∼0.25 mg DW L−1), increased the phosphate removal by 62–175% when compared to the reference conditions. A 10-day period of biomass P-deficiency also boosted the polyphosphate accumulation and protein productivity, increasing them up to 40 and 46.8 times, respectively, if compared to reference conditions. At the same time, optimization algorithm model results suggested one-day biomass P-starvation with low initial biomass concentration as the optimum combination to achieve the highest performance while the initial phosphate concentration had less impact. The initial conditions suggested by the optimization model were validated in a sequencing batch photobioreactor, giving 101.7 and 138.0% more phosphate removal and polyphosphate accumulation, compared to the reference conditions. The obtained results present microalgae exposure to phosphorus stress as a supplementary tool for wastewater post-treatment targeted on rapid phosphorus removal.