We re-examine what controls the deep ocean N:P ratio in the light of recent findings that the C:N:P stoichiometry of phytoplankton varies with growth rate, nutrient and light limitation, species and phylum, and that N2-fixation may be limited by Fe, temperature and/or light in large parts of the world ocean. In particular, we assess whether a systematic change in phytoplankton stoichiometry can alter the deep ocean N:P ratio. To do this we adapt recent models to include non-Redfieldian stoichiometry of phytoplankton and restriction of N2-fixers to a fraction of the surface ocean. We show that a systematic change in phytoplankton C:N:P can alter the concentrations of NO3 and PO4 in the deep ocean but cannot greatly alter their ratio, unless it also alters the N:P threshold for N2-fixation. This occurs if competitive dynamics set the N:P threshold for N2-fixation, in which case it remains close to the N:P requirement of non-fixers (rather than that of N2-fixers) and consequently so does the deep ocean N:P ratio. Then, even if N2-fixers are restricted to a fraction of the surface ocean, they reach higher densities there, minimising variations in deep ocean N:P. Theoretical limits on the N:P requirements of phytoplankton suggest that whilst the deep ocean has been well oxygenated (i.e. since the Neoproterozoic, with the possible exception of Oceanic Anoxic Events), its N:P ratio is unlikely to have varied by more than a factor of two in either direction. Within these bounds, evolutionary changes in phytoplankton composition, and increased phosphorus weathering due to the biological colonisation of the land surface, are predicted to have driven long-term changes in ocean composition.