A mesophilic methanogenic culture, designated JL01, was isolated from Holocene permafrost in the Russian Arctic. After long-term extensive cultivation at 15 °C, it turned out to be a tied binary culture of archaeal (JL01) and bacterial (Sphaerochaeta associata GLS2) strains. Strain JL01 was a strict anaerobe and grew on methanol, acetate, and methylamines as energy and carbon sources. Cells were irregular coccoid, non-motile, non-spore-forming, and Gram-stain-positive. Optimum conditions for growth were 24–28 °C, pH 6.8–7.3, and 0.075–0.1 M NaCl. Phylogenetic tree reconstructions based on 16S rRNA and concatenated alignment of broadly conserved protein-coding genes revealed 16S rRNA’s close relation to Methanosarcina mazei S-6T (similarity 99.5%). The comparison of whole genomic sequences (ANI) of the isolate and the type strain of M. mazei was 98.5%, which is higher than the values recommended for new species. Thus, strain JL01 (=VKM B-2370 = JCM 31898) represents the first M. mazei isolated from permanently subzero Arctic sediments. The long-term co-cultivation of JL01 with S. associata GLS2T showed the methane production without any additional carbon and energy sources. Genome analysis of S. associata GLS2T revealed putative genes involved in methanochondroitin catabolism.