Gusev crater has long been considered the site of a lake early in Martian history, but the Mars Exploration Rover Spirit found no apparent evidence of lake deposits along its 7 km traverse from 2004 to 2010. Although outcrops rich in Mg-Fe carbonate, dubbed Comanche, were discovered in the Noachian-aged Columbia Hills, they were inferred to result from volcanic hydrothermal activity. We now find evidence that the alteration of the Comanche outcrops is consistent with evaporative precipitation of low-temperature, near-surface solutions derived from limited water-rock interaction with rocks equivalent to nearby outcrops called Algonquin. Additional observations show that the Algonquin outcrops are remnants of volcanic tephra that covered the Columbia Hills and adjacent plains well before emplacement of basalt flows onto the floor of Gusev crater. Water-limited leaching of formerly widespread Algonquin-like tephra deposits by ephemeral waters, followed by transport and evaporative precipitation of the fluids into the Comanche outcrops, can explain their chemical, mineralogical, and textural characteristics.