The rise of oxygen on the early Earth (about 2.4 billion years ago) caused a reorganization of marine nutrient cycles, including that of nitrogen, which is important for controlling global primary productivity. However, current geochemical records lack the temporal resolution to address the nature and timing of the biogeochemical response to oxygenation directly. Here we couple records of ocean redox chemistry with nitrogen isotope (15N/14N) values from approximately 2.31-billion-year-old shales of the Rooihoogte and Timeball Hill formations in South Africa, deposited during the early stages of the first rise in atmospheric oxygen on the Earth (the Great Oxidation Event). Our data fill a gap of about 400 million years in the temporal 15N/14N record and provide evidence for the emergence of a pervasive aerobic marine nitrogen cycle. The interpretation of our nitrogen isotope data in the context of iron speciation and carbon isotope data suggests biogeochemical cycling across a dynamic redox boundary, with primary productivity fuelled by chemoautotrophic production and a nitrogen cycle dominated by nitrogen loss processes using newly available marine oxidants. This chemostratigraphic trend constrains the onset of widespread nitrate availability associated with ocean oxygenation. The rise of marine nitrate could have allowed for the rapid diversification and proliferation of nitrate-using cyanobacteria and, potentially, eukaryotic phytoplankton.