High-resolution spacecraft data reveal the presence of a distinctive unit on the upper reaches of the floor of Mangala Valles, an ancient outflow channel on Mars. In contrast to abundant evidence for scour, intense erosion, and hydrodynamic shaping typical of the floors and margins of Mangala and other outflow channels, this unit is smooth-surfaced, has cuspate margins, is superposed on the scoured valley floor, and is extensively pitted. We interpret this unit to be the sublimation lag deposit derived from an ice thermal boundary layer on the aqueous flood that formed the outflow channel system, and the remnant of floodwaters trapped in channel lows. This interpretation further supports the likelihood that climate conditions at the time of emplacement were similar to the hyper-arid cold desert conditions of today. Frozen floodwaters from the ancient martian subsurface could still be preserved in these deposits, representing attractive and accessible exobiological exploration objectives.