Ice-rich permafrost coasts in the Arctic are susceptible to a variety of changing environmental factors, all of which currently point to increasing coastal erosion rates and mass fluxes of sediment and carbon to the shallow arctic shelf seas. Coastal erosion and flooding inundate terrestrial permafrost with seawater and create submarine permafrost. Permafrost begins to warm under marine conditions, which can destabilize the sea floor and may release greenhouse gases. The rate and spatial distribution of subsea permafrost degradation in the Laptev, East Siberian and Chukchi seas, which together comprise more than half of the Arctic Ocean continental shelf, remain poorly explored. We report on the transition of terrestrial to subsea permafrost at four coastal sites in the Laptev Sea: Cape Mamontov Klyk in the western Laptev Sea, and Buor Khaya Peninsula, Muostakh Island and the Bykovsky Peninsula in the central Laptev Sea. We use coastal erosion rates from about the last 70 years to estimate the period of inundation at these sites. Combined with direct (drilling and temperature) and indirect (geophysical) observations of thaw depths of ice-bonded permafrost, we estimate recent degradation rates of permafrost over the past centuries. Based on these observations, the unfrozen sediment layer overlying ice-bonded permafrost increased from less than a meter at the shoreline to over 30 m below seabed with increasing distance from the shoreline at our study sites, with high spatial variability between and within sites. Observed temperatures of the sediment ranged from -5 °C to positive temperatures. In coastal sediments, it is difficult to establish an age-depth model, making corroboration of estimated degradation rates a challenge. Nonetheless, as the thickness of the unfrozen sediment layer increases over time, the vertical thermal and salt concentration gradients decrease, slowing the downward heat and mass fluxes responsible for degradation. High sedimentation rates and ice contents probably stabilize subsea permafrost. We suggest that permafrost degradation relevant to gas flow is likely to have occurred where permafrost warmed prior to inundation.