Volcanic rootless constructs (VRCs) are the products of explosive lava-water interactions. VRCs are significant because they imply the presence of active lava and an underlying aqueous phase (e.g., groundwater or ice) at the time of their formation. Combined mapping of VRC locations, age-dating of their host lava surfaces, and thermodynamic modeling of lava-substrate interactions can therefore constrain where and when water has been present in volcanic regions. This information is valuable for identifying fossil hydrothermal systems and determining relationships between climate, near-surface water abundance, and the potential development of habitable niches on Mars. We examined the western Tartarus Colles region (25–27°N, 170–171°E) in northeastern Elysium Planitia, Mars, and identified 167 VRC groups with a total area of ∼2000 km2. These VRCs preferentially occur where lava is ∼60 m thick. Crater size-frequency relationships suggest the VRCs formed during the late to middle Amazonian. Modeling results suggest that at the time of VRC formation, near-surface substrate was partially desiccated, but that the depth to the midlatitude ice table was ≲42 m. This ground ice stability zone is consistent with climate models that predict intermediate obliquity (∼35°) between 75 and 250 Ma, with obliquity excursions descending to ∼25–32°. For lava thicknesses ranging from 30 to 60 m and ground ice fractions ranging from 0.1 to 0.3, an ice volume of ∼4–23 km3 could have been melted and/or vaporized by the time the lava solidified, and the associated hydrothermal systems could have retained temperatures >273 K for up to ∼1300 years.