Geologic features resembling terrestrial water-carved gullies imply that liquid water has flowed recently on the surface of Mars and challenge our views of the present-day low-temperature environment. We evaluate two possible mechanisms for the formation of liquid water under environmental conditions that we expect to have existed on Mars in its recent past. First, we examine the stability of ground ice in the permafrost and the potential for melting near-surface ground ice (in the top few meters of soil) by solar heating and subsurface conduction. Second, we examine the potential for melting and refreezing of ice at shallow depths due to geothermal heating. We find that near-surface ground ice does not reach the melting point of water under a range of conditions of soil thermophysical properties, latitudes, obliquities, and surface slopes. The atmosphere remains too dry for the ground ice to melt, even at high obliquity; instead, ice sublimates before reaching melting temperatures. However, the presence of salts in concentrations of 15--40% can adequately lower the melting point to allow melting to occur. We also find that a combination of a global average geothermal heat flux and a thick, low-conductivity, unconsolidated regolith raises the depth of the melting isotherm to less than a few hundred meters from the surface. Orbitally induced oscillations in the mean annual surface temperature can cause freezing cycles in a confined aquifer at this depth. Freezing pressures generated are adequate to fracture ice-cemented ground and allow water to escape to the surface, similar to the formation and evolution of terrestrial pingos in shallow permafrost. Both mechanisms are possible; however, the geothermal mechanism is consistent with the observations of the distribution of gullies, while the salty near-surface ground ice mechanism is not. Further observational tests that can be performed with existing and future spacecraft are suggested. ¿ 2001 American Geophysical Union