Vast quantities of carbon are stored in shallow Arctic reservoirs, such as submarine and terrestrial permafrost. Submarine permafrost on the East Siberian Arctic Shelf started warming in the early Holocene, several thousand years ago. However, the present state of the permafrost in this region is uncertain. Here, we present data on the temperature of submarine permafrost on the East Siberian Arctic Shelf using measurements collected from a sediment core, together with sonar-derived observations of bubble flux and measurements of seawater methane levels taken from the same region. The temperature of the sediment core ranged from -1.8 to 0 degrees C. Although the surface layer exhibited the lowest temperatures, it was entirely unfrozen, owing to significant concentrations of salt. On the basis of the sonar data, we estimate that bubbles escaping the partially thawed permafrost inject 100-630 mg methane m(-2) d(-1) into the overlying water column. We further show that water-column methane levels had dropped significantly following the passage of two storms. We suggest that significant quantities of methane are escaping the East Siberian Shelf as a result of the degradation of submarine permafrost over thousands of years. We suggest that bubbles and storms facilitate the flux of this methane to the overlying ocean and atmosphere, respectively.