Thermokarst lakes formed across vast regions of Siberia and Alaska during the last deglaciation and are thought to be a net source of atmospheric methane and carbon dioxide during the Holocene epoch. However, the same thermokarst lakes can also sequester carbon, and it remains uncertain whether carbon uptake by thermokarst lakes can offset their greenhouse gas emissions. Here we use field observations of Siberian permafrost exposures, radiocarbon dating and spatial analyses to quantify Holocene carbon stocks and fluxes in lake sediments overlying thawed Pleistocene-aged permafrost. We find that carbon accumulation in deep thermokarst-lake sediments since the last deglaciation is about 1.6 times larger than the mass of Pleistocene-aged permafrost carbon released as greenhouse gases when the lakes first formed. Although methane and carbon dioxide emissions following thaw lead to immediate radiative warming, carbon uptake in peat-rich sediments occurs over millennial timescales. We assess thermokarst-lake carbon feedbacks to climate with an atmospheric perturbation model and find that thermokarst basins switched from a net radiative warming to a net cooling climate effect about 5,000 years ago. High rates of Holocene carbon accumulation in 20 lake sediments (47 ± 10 grams of carbon per square metre per year; mean ± standard error) were driven by thermokarst erosion and deposition of terrestrial organic matter, by nutrient release from thawing permafrost that stimulated lake productivity and by slow decomposition in cold, anoxic lake bottoms. When lakes eventually drained, permafrost formation rapidly sequestered sediment carbon. Our estimate of about 160 petagrams of Holocene organic carbon in deep lake basins of Siberia and Alaska increases the circumpolar peat carbon pool estimate for permafrost regions by over 50 per cent (ref. 6). The carbon in perennially frozen drained lake sediments may become vulnerable to mineralization as permafrost disappears, potentially negating the climate stabilization provided by thermokarst lakes during the late Holocene.