At the mid-latitudes of Utopia Planitia (UP), Mars, a suite of spatially-associated landforms exhibit geomorphological traits that, on Earth, would be consistent with periglacial processes and the possible freeze-thaw cycling of water. The suite comprises small-sized polygonally-patterned ground, polygon-junction and -margin pits, and scalloped, rimless depressions. Typically, the landforms incise a dark-toned terrain that is thought to be ice-rich. Here, we investigate the dark-toned terrain by using high resolution images from the HiRISE as well as near-infrared spectral-data from the OMEGA and CRISM. The terrain displays erosional characteristics consistent with a sedimentary nature and near-infrared spectra characterised by a blue slope similar to that of weathered basaltic-tephra. We also describe volcanic terrain that is dark-toned and periglacially-modified in the Kamchatka mountain-range of eastern Russia. The terrain is characterised by weathered tephra inter-bedded with snow, ice-wedge polygons and near-surface excess ice. The excess ice forms in the pore space of the tephra as the result of snow-melt infiltration and, subsequently, in-situ freezing. Based on this possible analogue, we construct a three-stage mechanism that explains the possible ice-enrichment of a broad expanse of dark-toned terrain at the mid-latitudes of UP: (1) the dark-toned terrain accumulates and forms via the regional deposition of sediments sourced from explosive volcanism; (2) the volcanic sediments are blanketed by atmospherically-precipitated (H2O) snow, ice or an admixture of the two, either concurrent with the volcanic-events or between discrete events; and, (3) under the influence of high obliquity or explosive volcanism, boundary conditions tolerant of thaw evolve and this, in turn, permits the migration, cycling and eventual formation of excess ice in the volcanic sediments. Over time, and through episodic iterations of this scenario, excess ice forms to decametres of depth. (C) 2015 Elsevier B.V. All rights reserved.