Thawing subsea permafrost in the East Siberian Arctic Seas releases methane, a potent greenhouse gas. Using molecular fossils in sediments, we traced aerobic methane oxidation as a proxy of enhanced methane cycling across the Laptev Sea, including in regions once thought low in emissions. This approach captures long-term patterns of methane cycling over years-decades , overcoming limits of short-term seawater measurements and highlights the importance of the Laptev Sea in Arctic methane cycling.