Thawing submarine permafrost is a source of methane to the subsurface biosphere. Methane oxidation in submarine permafrost sediments has been proposed, but the responsible microorganisms remain uncharacterized. We analyzed archaeal communities and identified distinct anaerobic methanotrophic assemblages of marine and terrestrial origin (ANME-2a/b, ANME-2d) both in frozen and completely thawed submarine permafrost sediments. Besides archaea potentially involved in anaerobic oxidation of methane (AOM) we found a large diversity of archaea mainly belonging to Bathyarchaeota, Thaumarchaeota, and Euryarchaeota. Methane concentrations and δ13C-methane signatures distinguish horizons of potential AOM coupled either to sulfate reduction in a sulfate-methane transition zone (SMTZ) or to the reduction of other electron acceptors, such as iron, manganese or nitrate. Analysis of functional marker genes (mcrA) and fluorescence in situ hybridization (FISH) corroborate potential activity of AOM communities in submarine permafrost sediments at low temperatures. Modeled potential AOM consumes 72–100% of submarine permafrost methane and up to 1.2 Tg of carbon per year for the total expected area of submarine permafrost. This is comparable with AOM habitats such as cold seeps. We thus propose that AOM is active where submarine permafrost thaws, which should be included in global methane budgets.