Sustained release of methane (CH4) to the atmosphere from thawing Arctic permafrost may be a positive and significant feedback to climate warming. Atmospheric venting of CH4 from the East Siberian Arctic Shelf (ESAS) was recently reported to be on par with flux from the Arctic tundra; however, the future scale of these releases remains unclear. Here, based on results of our latest observations, we show that CH4 emissions from this shelf are likely to be determined by the state of subsea permafrost degradation. We observed CH4 emissions from two previously understudied areas of the ESAS: the outer shelf, where subsea permafrost is predicted to be discontinuous or mostly degraded due to long submergence by seawater, and the near shore area, where deep/open taliks presumably form due to combined heating effects of seawater, river run-off, geothermal flux and pre-existing thermokarst. CH4 emissions from these areas emerge from largely thawed sediments via strong flare-like ebullition, producing fluxes that are orders of magnitude greater than fluxes observed in background areas underlain by largely frozen sediments. We suggest that progression of subsea permafrost thawing and decrease in ice extent could result in a significant increase in CH4 emissions from the ESAS.