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. 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. While methane and carbon dioxide emissions following thaw lead to immediate radiative warming, carbon uptake in peat-rich sediments occurs over millennial time scales. With the help of an atmospheric perturbation model we assess thermokarst-lake carbon feedbacks to climate and find that thermokarst basins switched from a net radiative warming to a net cooling climate effect about 5000 years ago. High rates of Holocene carbon accumulation in lake sediments (47 ± 10 g C m-2 a-1, mean ± SE, n=20 lakes) 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 Pg 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 percent. 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.