Azolla spp., a water fern often used for phytoremediation, is a strong phosphorus (P) accumulator due to its high growth rate and N2 fixing symbionts (diazotrophs). It is known that plant growth is stimulated by P, but the nature of the interactive response of both symbionts along a P gradient, and related changes in growth-limiting factors, are unclear. We determined growth, and N and P sequestration rates of Azolla filiculoides in N-free water at different P concentrations. The growth response appeared to be biphasic and highest at levels ≥10 P µmol l-1. Diazotrophic N sequestration increased upon P addition, and rates were three times higher at high P than at low P. At 10 µmol P l-1, N sequestration rates reached its maximum and A. filiculoides growth became saturated. Due to luxury consumption, P sequestration rates increased until 50 µmol P l-1. At higher P concentrations (≥50 µmol l-1), however, chlorosis occurred that seems to be caused by iron- (Fe-), and not by N-deficiency. We demonstrate that traits of the complete symbiosis in relation to P and Fe availability determine plant performance, stressing the role of nutrient stoichiometry. The results are discussed regarding Azolla's potential use in a bio-based economy.