The transition from onshore to offshore permafrost during periods of low relative sea level rise is often the result of coastal retreat. Along the Laptev Sea coastline, ice-rich syngenetic permafrost is particularly susceptible to erosion due to changing climate, and coastal retreat floods about 10 km2 of permafrost each year. Changes to permafrost immediately after flooding provide an opportunity to study the mechanism of submarine permafrost degradation in general. Recent studies have drawn a link between observed methane release on the Laptev Sea shelf and surmised permafrost degradation. We combine direct observations of permafrost and methane to investigate the possibility of methane release from permafrost as a source. Our studies focus on a site in Buor Khaya Bay in the central Laptev Sea, for which coastal retreat rates have been studied. Following geophysical reconnaissance, we drilled a 52 m deep core in the near-shore zone of the eastern shore of Buor Khaya Bay and measured the permafrost temperature in the resulting borehole. Comparison of the submarine permafrost temperature to temperatures on land reveal warming of permafrost by 8 to 10 °C over a period of less than a millennium. During this time, the top of the ice-bearing permafrost (IBPF) degraded from 0 to 28.8 m b.s.l. at the borehole site, a mean degradation rate of almost 3 cm per year. Geoelectric resistivity measurements corroborate this observation and show a decline of the IBPF with increasing distance from shore. Similar to many other Siberian locations, the deeper permafrost at the study site contained less organic carbon by orders of magnitude when compared to the overlying syngenetic ice complex deposits. The same held true for methane concentrations in the frozen permafrost. Our data suggest that these comparatively low concentrations of methane are oxidized in the sediment column upon thawing. Analyses of the sediment and pore water chemistry demonstrate that sea water is probably advected to the IBPF, which contributes to permafrost degradation and provides sulfate for methane oxidation at the top of the thawing permafrost.