The degradation of permafrost beneath the seabed on the East Siberian Shelf has been implicated in the release of greenhouse gases, especially methane, and the potential de-stabilization of gas hydrates. We investigate the degradation of subsea permafrost using geophysical methods, drilling and temperature measurements. Recovered subsea sediments offer an opportunity to investigate sediment composition, reconstruct permafrost degradation processes, and to better understand the consequences of this degradation. A 52 m deep borehole was drilled about 800 m offshore to the west of the Buor Khaya Peninsula in the central Laptev Sea. Coastal exposures and an onshore borehole revealed “ice complex” stratigraphy with high ice and carbon contents. The landscape of the Buor Khaya Peninsula, however, has undergone substantial degradation, so that isolated islands of relatively intact ice complex cover about 15% of the area among a palimpsest of thermokarst basins. The subsea sediment was mostly sandy with spatially highly variable carbon contents and isolated layers of woody plant remains probably deposited in a fluvial environment before freezing. Ice-bonded permafrost was encountered at 28 m b.s.l. The western coast of the Buor Khaya Peninsula has been retreating at between 1 and 2 m per year. The position of the ice-bonded permafrost table with distance from shore suggests that subsea permafrost degrades at a mean rate of 3 to 4 cm a-1 following erosion. Methane was entrapped throughout the frozen sediment suggesting the mobilization of methane along with permafrost degradation at this site.