Geochemical evidence suggests that there was a delay of several hundred million years between the evolution of oxygenic photosynthesis and the accumulation of oxygen in Earth’s atmosphere. The deep ocean appears to have remained euxenic for several hundred million years after the atmosphere became oxygenated. In this paper we examine the possibility that the extraordinary delay in the oxidation of the atmosphere and oceans was caused by a biogeochemical “bottleneck” imposed by metabolic feedbacks between carbon burial, net oxygen production, and the evolution of the nitrogen cycle in the Proterozoic oceans. Whereas under anoxic conditions oceanic ammonium would have been relatively stable, as oxygen concentrations rose, nitrification and subsequent denitrification would have rapidly removed fixed inorganic nitrogen from the oceans. Denitrification would have imposed a strong constraint on the further rise of free oxygen by depriving oxygenic photoautotrophs of an essential nutrient (that is, fixed inorganic nitrogen). To examine the dynamic interactions between oxygen and nitrogen cycling, we developed a five box model that incorporates the salient features of the oxygen, nitrogen and carbon cycles, ocean circulation, and ocean-atmosphere gas-exchange. Model simulations, initiated under anaerobic conditions with no free oxygen in the atmosphere or ocean, are characterized by an initially reduced deep ocean with abundant ammonium, followed by an extended period when neither form of fixed nitrogen is stable, and a fully oxidized phase with abundant nitrate. We infer that, in the process of oxidizing the early Proterozoic ocean, the system had to go through a nitrogen-limited phase during which time export production was severely attenuated. Our studies suggest that the presence of shallow seas with increased organic matter burial was a critical factor determining the concentration of oxygen in the ocean and atmosphere, while the phosphate concentration played a key role in determining the rate of oxygenation of the deep ocean.