Methane production in thawing permafrost can be substantial, yet often evolves after long lag phases or is even lacking. A central question is to which extent the production of methane after permafrost thaw is determined by the initial methanogenic community. We quantified the production of methane relative to carbon dioxide (CO2) and enumerated methanogenic (mcrA) gene copies in long-term (2–7 years) anoxic incubations at 4 °C using interglacial and glacial permafrost samples of Holocene and Pleistocene, including Eemian, origin. Changes in archaeal community composition were determined by sequencing of the archaeal 16S rRNA gene. Long-term thaw stimulated methanogenesis where methanogens initially dominated the archaeal community. Deposits of interstadial and interglacial (Eemian) origin, formed under higher temperatures and precipitation, displayed the greatest response to thaw. At the end of the incubations, a substantial shift in methanogenic community composition and a relative increase in hydrogenotrophic methanogens had occurred except for Eemian deposits in which a high abundance of potential acetoclastic methanogens were present. This study shows that only anaerobic CO2 production but not methane production correlates significantly with carbon and nitrogen content and that the methanogenic response to permafrost thaw is mainly constrained by the paleoenvironmental conditions during soil formation.