Recent hypotheses, based on atmospheric records and models, suggest that permafrost carbon (PF-C) accumulated during the last glaciation may have been an important source for the atmospheric CO2 rise during post-glacial warming. However, direct physical indications for such PF-C release have so far been absent. Here we use the Laptev Sea (Arctic Ocean) as an archive to investigate PF-C destabilization during the last glacial-interglacial period. Our results show evidence for massive supply of PF-C from Siberian soils as a result of severe active layer deepening in response to the warming. Thawing of PF-C must also have brought about an enhanced organic matter respiration and, thus, these findings suggest that PF-C may indeed have been an important source of CO2 across the extensive permafrost domain. The results challenge current paradigms on the post-glacial CO2 rise and, at the same time, serve as a harbinger for possible consequences of the present-day warming of PF-C soils.