We determine Hg concentrations of various deposits in Siberia’s deep permafrost and link sediment properties and Hg enrichment to establish a first Hg inventory of late Pleistocene permafrost down to a depth of 36 m below surface. As Arctic warming is transforming the ice-rich permafrost of Siberia, sediment is released and increases the flux of particulates to the Arctic shelf seas through thawing coasts, lakeshores, and river floodplains. Heavy metals within soils and sediments are also released and may increasingly enter Arctic waters and the biological food chain. High levels of mercury (Hg) have been reported from shallow soils across the Arctic. Rapid thawing is now mobilizing sediment from deeper strata, but so far little is known about Hg concentrations in deep permafrost. Here, forty-one samples from sediment successions at seven sites and of different states of permafrost degradation on Bykovsky Peninsula (northern Yakutian coast) and in the Yukechi Alas region (Central Yakutia) were analyzed for Hg, total carbon, total nitrogen, and total organic carbon as well as grain-size distribution, bulk density, and mass specific magnetic susceptibility. We show average Hg concentrations of 9.72 ± 9.28 μg kg-1 in the deep sediments, an amount comparable to the few previous Arctic studies existing, and a significant correlation of Hg content with total organic carbon, total nitrogen, grain-size distribution, and mass specific magnetic susceptibility. Hg concentrations are higher in the generally sandier sediments of the Bykovsky Peninsula than in the siltier sediments of the Yukechi Alas. The ratio of Hg to total organic carbon in this study is 2.57 g kg-1, including samples with very low carbon content. We conclude that many deep permafrost sediments, some of which have been frozen for millennia, contain elevated concentrations of Hg and the stock of Hg ready to be released by erosion is of significance for the Arctic ecosystem. The Hg mobilized may accumulate on the way to or in the shallow sea, and where it enters into active biogeochemical cycles of aquatic systems it may concentrate in food webs. Our study highlights the need for better understanding Hg stocks and Hg release from permafrost.