Salinity-driven density stratification of the upper Arctic Ocean isolates sea-ice cover and cold, nutrient-poor surface waters from underlying warmer, nutrient-rich waters. Recently, stratification has strengthened in the western Arctic but has weakened in the eastern Arctic; it is unknown if these trends will continue. Here we present foraminifera-bound nitrogen isotopes from Arctic Ocean sediments since 35,000 years ago to reconstruct past changes in nutrient sources and the degree of nutrient consumption in surface waters, the latter reflecting stratification. During the last ice age and early deglaciation, the Arctic was dominated by Atlantic-sourced nitrate and incomplete nitrate consumption, indicating weaker stratification. Starting at 11,000 years ago in the western Arctic, there is a clear isotopic signal of Pacific-sourced nitrate and complete nitrate consumption associated with the flooding of the Bering Strait. These changes reveal that the strong stratification of the western Arctic relies on low-salinity inflow through the Bering Strait. In the central Arctic, nitrate consumption was complete during the early Holocene, then declined after 5,000 years ago as summer insolation decreased. This sequence suggests that precipitation and riverine freshwater fluxes control the stratification of the central Arctic Ocean. Based on these findings, ongoing warming will cause strong stratification to expand into the central Arctic, slowing the nutrient supply to surface waters and thus limiting future phytoplankton productivity.