Large Hesperian-aged (~3.7 Ga) layered deposits of sulfate-rich sediments in the equatorial regions of Mars have been suggested to be evidence for ephemeral playa environments. But early Mars may not have been warm enough to support conditions similar to what occurs in arid environments on Earth. Instead cold, icy environments may have been widespread. Under cryogenic conditions sulfate formation might be blocked, since kinetics of silicate weathering are typically strongly retarded at temperatures well below 0 °C. But cryo-concentration of acidic solutions may counteract the slow kinetics. Here we show that cryo-concentrated acidic brines rapidly chemically weather olivine minerals and form sulfate minerals at temperatures as low as -60 °C. These experimental results demonstrate the viability of sulfate formation under current Martian conditions, even in the polar regions. An ice-hosted sedimentation and weathering model may provide a compelling description of the origin of large Hesperian-aged layered sulfate deposits on Mars.