Nutrient limitation of oceanic primary production exerts a fundamental control on marine food webs and the flux of carbon into the deep ocean. The extensive boundaries of the oligotrophic sub-tropical gyres collectively define the most extreme transition in ocean productivity, but little is known about nutrient limitation in these zones. Here we present the results of full-factorial nutrient amendment experiments conducted at the eastern boundary of the South Atlantic gyre. We find extensive regions in which the addition of nitrogen or iron individually resulted in no significant phytoplankton growth over 48 hours. However, the addition of both nitrogen and iron increased concentrations of chlorophyll a by up to approximately 40-fold, led to diatom proliferation, and reduced community diversity. Once nitrogen-iron co-limitation had been alleviated, the addition of cobalt or cobalt-containing vitamin B12 could further enhance chlorophyll a yields by up to threefold. Our results suggest that nitrogen-iron co-limitation is pervasive in the ocean, with other micronutrients also approaching co-deficiency. Such multi-nutrient limitations potentially increase phytoplankton community diversity.