Cold environments are common throughout the Galaxy. We are conducting a series of experiments designed to probe the low-temperature limits for growth in selected methanogenic and halophilic Archaea. This paper presents initial results for two mesophiles, a methanogen, Methanosarcina acetivorans, and a halophile, Halobacterium sp. NRC-1, and for two Antarctic cold-adapted Archaea, a methanogen, Methanococcoides burtonii, and a halophile, Halorubrum lacusprofundi. Neither mesophile is active at temperatures below 5 °C, but both cold-adapted microorganisms show significant growth at sub-zero temperatures (−2 °C and −1 °C, respectively), extending previous low-temperature limits for both species by 4–5 °C. At low temperatures, both H. lacusprofundi and M. burtonii form multicellular aggregates, which appear to be embedded in extracellular polymeric substances. This is the first detection of this phenomenon in Antarctic species of Archaea at cold temperatures. The low-temperature limits for both psychrophilic species fall within the temperature range experienced on present-day Mars and could permit survival and growth, particularly in sub-surface environments. We also discuss the results of our experiments in the context of known exoplanet systems, several of which include planets that intersect the Habitable Zone. In most cases, those planets follow orbits with significant eccentricity, leading to substantial temperature excursions. However, a handful of the known gas giant exoplanets could potentially harbour habitable terrestrial moons.