The Bølling-Allerød interstadial (14,700–12,900 years before present), during the last deglaciation, was characterized by rapid warming and sea level rise. Yet, the response of the Arctic terrestrial cryosphere during this abrupt climate change remains thus far elusive. Here we present a multi-proxy analysis of a sediment record from the northern Svalbard continental margin, an area strongly influenced by sea ice export from the Arctic, to elucidate sea level - permafrost erosion connections. We show that permafrost-derived material rich in biospheric carbon became the dominant source of sediments at the onset of the Bølling-Allerød, despite the lack of direct connections with permafrost deposits. Our results suggest that the abrupt temperature and sea level rise triggered massive erosion of coastal ice-rich Yedoma permafrost, possibly from Siberian and Alaskan coasts, followed by long-range sea ice transport towards the Fram Strait and the Arctic Ocean gateway. Overall, we show how coastal permafrost is susceptible to large-scale remobilization in a scenario of rapid climate variability.