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.