In this study we experimentally tested the hypothesis that phosphorus was the primary nutrient limiting phytoplankton and bacterial growth in the eastern Mediterranean Sea, and examined the spatial variability in P limitation during winter. Complementary measurements were employed using water sampled during January 1995 from nine pelagic stations east of the Straits of Sicily. Ambient concentrations of inorganic P (P_i) in the upper 50 m of the water column in seven of the stations were 20–40 nM. The upper limit of bioavailable P ranged from 6 to 18 nM, suggesting severe P shortage. Orthophosphate turnover time ranged from 2 to 7 h in those P_i‐depleted waters. In nutrient‐enrichment bioassays using subsurface water from the Ionian and Levantine basins, P addition caused significant increases in bacterial activity, bacterial numbers, and chlorophyll a relative to unenriched controls. The addition of NH₄⁺ + Fe + EDTA did not have these effects. In a similar bioassay using Cretan water, microbial growth was obtained even in the unemriched controls, suggesting that other factors (e.g. grazing, light) were influential. Higher ambient P, concentrations were encountered in the Cretan Sea (90 nM) and in the core of the Rhodes gyre (210 nM), where our sampling coincided with a convective mixing event. In those stations, P sufficiency was indicated. We concluded that in the pelagic waters of the eastern Mediterranean in winter, P was the primary limiting nutrient when other factors (such as light or grazing) did not control microbial biomass or activity. In ultra‐oligotrophic waters, a delicate and dynamic balance differentiates between times when the microbial populations are nutrient limited and times when growth becomes limited by other factors. We caution that the interpretation of data obtained using conventional methods that were developed and tested in more enriched systems may not be valid in ultra‐oligotrophic systems.