Large positive anomalies in lower troposphere methane (CH₄) in early fall of nearly every year (2003 to 2015) led to an average atmospheric CH₄ growth of 3.06 to 3.49 ppb yr^-1 for the Barents and Kara Seas (BKS). At the same time, sea surface temperature (SST) increased from 0.0018 to 0.15 °C yr^-1 while sea ice coverage decreased. Large positive CH₄ anomalies were discovered around Franz Josef Land (FJL) and offshore west Novaya Zemlya with smaller CH₄ enhancement and growth near Svalbard, downstream and north of known seabed CH₄ seepage. The strongest SST increase each year was in the southeast Barents Sea in June due to strengthening of the warm Murman Current (MC) and in the south Kara Sea in September. We propose that atmospheric CH₄ increase is occurring due to seepage from the petroleum reservoirs underlying the BKS and thawing of subsea permafrost and hydrates which then ventilates to the atmosphere from seasonal deepening of the surface ocean mixed layer and also from “methane shoaling” where currents transport deep water CH₄ into shallower waters. Continued strengthening heat transfer by the MC to the BKS will contribute to further warming (with the Barents Sea projected ice-free around 2030) and marine CH₄ emissions to the atmosphere.