The Arctic Ocean has an important role in Earth's climate, both through surface processes(1) such as sea-ice formation and transport, and through the production and export of waters at depth that contribute to the global thermohaline circulation(2,3). Deciphering the deep Arctic Ocean's palaeo-oceanographic history is a crucial part of understanding its role in climatic change. Here we show that sedimentary ratios of the radionuclides thorium-230 (Th-230) and protactinium-231 (Pa-231), which are produced in sea water and removed by particle scavenging on timescales of decades to centuries, respectively(4), record consistent evidence for the export of 231Pa from the deep Arctic and may indicate continuous deep-water exchange between the Arctic and Atlantic oceans throughout the past 35,000 years. Seven well-dated box-core records provide a comprehensive overview of Pa-231 and Th-230 burial in Arctic sediments during glacial, deglacial and interglacial conditions. Sedimentary Pa-231/Th-230 ratios decrease nearly linearly with increasing water depth above the core sites, indicating efficient particle scavenging in the upper water column and greater influence of removal by lateral transport at depth. Although the measured Th-230 burial is in balance with its production in Arctic sea water, integrated depth profiles for all time intervals reveal a deficit in Pa-231 burial that can be balanced only by lateral export in the water column. Because no enhanced sink for Pa-231 has yet been found in the Arctic, our records suggest that deep-water exchange through the Fram strait may export Pa-231. Such export may have continued for the past 35,000 years, suggesting a century-scale replacement time for deep waters in the Arctic Ocean since the most recent glaciation and a persistent contribution of Arctic waters to the global ocean circulation.