Thermokarst lakes cause abrupt and sustained permafrost degradation and have the potential to release large quantities of ancient carbon to the atmosphere. Despite concerns about how lakes will affect the permafrost carbon feedback, the magnitude of carbon dioxide and methane emissions from deep permafrost soils remains poorly understood. Here we incubated a very deep sediment core (20 m) to constrain the potential productivity of thawed Yedoma and underlying Quaternary sand and gravel deposits. Through radiocarbon dating, sediment incubations and sediment facies classifications, we show that extensive permafrost thaw can occur beneath lakes on timescales of decades to centuries. Although it has been assumed that shallow, aerobic carbon dioxide production will dominate the climate impact of permafrost thaw, we found that anaerobic carbon dioxide and methane production from deep sediments was commensurate with aerobic production on a per gram carbon basis, and had double the global warming potential at warmer temperatures. Carbon release from deep Arctic sediments may thus have a more substantial impact on a changing climate than currently anticipated. These environments are presently overlooked in estimates of the permafrost carbon feedback.