The Arctic Ocean has an important role in Earth's climate, both through surface processes such as sea-ice formation and transport, and through the production and export of waters at depth that contribute to the global thermohaline circulation. 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 ((230)Th) and protactinium-231 ((231)Pa), which are produced in sea water and removed by particle scavenging on timescales of decades to centuries, respectively, record consistent evidence for the export of (231)Pa 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 (231)Pa and (230)Th burial in Arctic sediments during glacial, deglacial and interglacial conditions. Sedimentary (231)Pa/(230)Th 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 (230)Th burial is in balance with its production in Arctic sea water, integrated depth profiles for all time intervals reveal a deficit in (231)Pa burial that can be balanced only by lateral export in the water column. Because no enhanced sink for (231)Pa has yet been found in the Arctic, our records suggest that deep-water exchange through the Fram strait may export (231)Pa. 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.