The future trajectory of greenhouse gas concentrations depends on interactions between climate and the biogeosphere(1,2). Thawing of Arctic permafrost could release significant amounts of carbon into the atmosphere in this century(3). Ancient Ice Complex deposits outcropping along the similar to 7,000-kilometre-long coastline of the East Siberian Arctic Shelf (ESAS)(4,5), and associated shallow subsea permafrost(6,7), are two large pools of permafrost carbon(8), yet their vulnerabilities towards thawing and decomposition are largely unknown(9-11). Recent Arctic warming is stronger than has been predicted by several degrees, and is particularly pronounced over the coastal ESAS region(12,13). There is thus a pressing need to improve our understanding of the links between permafrost carbon and climate in this relatively inaccessible region. Here we show that extensive release of carbon from these Ice Complex deposits dominates (57 +/- 2 per cent) the sedimentary carbon budget of the ESAS, the world's largest continental shelf, overwhelming the marine and topsoil terrestrial components. Inverse modelling of the dual-carbon isotope composition of organic carbon accumulating in ESAS surface sediments, using Monte Carlo simulations to account for uncertainties, suggests that 44 +/- 10 teragrams of old carbon is activated annually from Ice Complex permafrost, an order of magnitude more than has been suggested by previous studies(14). We estimate that about two-thirds (66 +/- 16 per cent) of this old carbon escapes to the atmosphere as carbon dioxide, with the remainder being re-buried in shelf sediments. Thermal collapse and erosion of these carbon-rich Pleistocene coastline and seafloor deposits may accelerate with Arctic amplification of climate warming(2,13).