Three microalgal species, Desmodesmus communis, Tetradesmus obliquus and Chlorella protothecoides were studied for enhanced phosphorus removal from municipal wastewater. Microalgae were first exposed to phosphorus deficit conditions for 7 and 14 days and then inoculated in filtered primary or secondary wastewater from a small municipal wastewater treatment plant at ambient temperature and CO2 concentration. D. communis and T. obliquus strains showed higher biomass growth rates in secondary wastewater after 7-day starvation period, while C. protothecoides grew better in the same effluent without starvation. All strains were able to achieve nearly complete (>99.9%) removal of dissolved inorganic phosphorus (DIP). Moreover, D. communis and T. obliquus showed ~89% DIP reduction within 24 h after 7-day phosphorus starvation. Dissolved inorganic nitrogen removal for all algal strains did not exceed 50% for any of the treatments. All three strains were able to store excess phosphorus within their cells as polyphosphate and the highest Poly-P content was observed in cultures grown in primary wastewater. Poly-P concentration in C. protothecoides reached 250 μg mg−1. At the same time no correlation between Poly-P and P removal was observed. The efficiency of nutrient (P) removal from municipal wastewater to ultra-low levels (<0.1 mg L−1) is closely linked to algae starvation and auxiliary factors, like environmental pH and N/P ratio.