Over much of the ocean's surface, productivity and growth are limited by a scarcity of bioavailable nitrogen. Sedimentary delta N-15 records spanning the last deglaciation suggest marked shifts in the nitrogen cycle during this time, but the quantification of these changes has been hindered by the complexity of nitrogen isotope cycling. Here we present a database of delta N-15 in sediments throughout the world's oceans, including 2,329 modern seafloor samples, and 76 timeseries spanning the past 30,000 years. We show that the delta N-15 values of modern seafloor sediments are consistent with values predicted by our knowledge of nitrogen cycling in the water column. Despite many local deglacial changes, the globally averaged delta N-15 values of sinking organic matter were similar during the Last Glacial Maximum and Early Holocene. Considering the global isotopic mass balance, we explain these observations with the following deglacial history of nitrogen inventory processes. During the Last Glacial Maximum, the nitrogen cycle was near steady state. During the deglaciation, denitrification in the pelagic water column accelerated. The flooding of continental shelves subsequently increased denitrification at the seafloor, and denitrification reached near steady-state conditions again in the Early Holocene. We use a recent parameterization of seafloor denitrification to estimate a 30-120% increase in benthic denitrification between 15,000 and 8,000 years ago. Based on the similarity of globally averaged delta N-15 values during the Last Glacial Maximum and Early Holocene, we infer that pelagic denitrification must have increased by a similar amount between the two steady states.