We report the first microbiological characterization of a terrestrial methane seep in a cryo-environment in the form of an Arctic hypersaline (∼24% salinity), subzero (-5 °C), perennial spring, arising through thick permafrost in an area with an average annual air temperature of -15 °C. Bacterial and archaeal 16S rRNA gene clone libraries indicated a relatively low diversity of phylotypes within the spring sediment (Shannon index values of 1.65 and 1.39, respectively). Bacterial phylotypes were related to microorganisms such as Loktanella, Gillisia, Halomonas and Marinobacter spp. previously recovered from cold, saline habitats. A proportion of the bacterial phylotypes were cultured, including Marinobacter and Halomonas, with all isolates capable of growth at the in situ temperature (-5 °C). Archaeal phylotypes were related to signatures from hypersaline deep-sea methane-seep sediments and were dominated by the anaerobic methane group 1a (ANME-1a) clade of anaerobic methane oxidizing archaea. CARD-FISH analyses indicated that cells within the spring sediment consisted of ∼84.0% bacterial and 3.8% archaeal cells with ANME-1 cells accounting for most of the archaeal cells. The major gas discharging from the spring was methane (∼50%) with the low CH(4)/C(2+) ratio and hydrogen and carbon isotope signatures consistent with a thermogenic origin of the methane. Overall, this hypersaline, subzero environment supports a viable microbial community capable of activity at in situ temperature and where methane may behave as an energy and carbon source for sustaining anaerobic oxidation of methane-based microbial metabolism. This site also provides a model of how a methane seep can form in a cryo-environment as well as a mechanism for the hypothesized Martian methane plumes.