Coastal erosion and relative sea-level rise inundate terrestrial permafrost with seawater and create submarine permafrost. Once flooded, permafrost begins to warm under marine conditions, which can destabilize the sea floor. The timing of inundation can be inferred from the rate of coastline retreat and the distance from the shoreline. Coastline retreat rates are inversely related to the inclination of the upper surface of submarine ice-bonded permafrost. Submarine permafrost thaw is considered to be a cause for recent observations of methane emissions from the seabed to the water column and atmosphere of the East Siberian shelf. A 52 m long core drilled from the sea ice in Buor Khaya Bay, central Laptev Sea revealed unfrozen sediment overlying ice-bonded permafrost. Dissolved methane and sulfate concentrations are inversely related along the core with higher methane and lower sulfate contents in the ice-bonded submarine permafrost relative to the overlying unfrozen sediment. The observed profiles of sediment pore water sulfate concentrations, as well as methane concentrations and methane stable carbon isotope ratios, indicate that methane from ice-bonded permafrost is oxidized at or immediately following thaw. Anaerobic oxidation of methane in the unfrozen sediment column between ice-bonded permafrost and the seabed makes it unlikely that methane from thawing submarine permafrost could reach the seabed.