Valley networks appear to be cut by liquid water, yet simulations suggest that early Mars could not have been warmed enough by a CO2-H2O greenhouse to permit rainfall. The vulnerability of an early atmosphere to impact erosion, the likely rapid scavenging of CO2 from the atmosphere by weathering, and the lack of detection of weathering products all support a cold early Mars. We explore the hypothesis that valley networks could have formed as a result of basal melting of thick snow and ice deposits. Depending on the heat flow, an early snowpack a few hundred meters to a few kilometers thick could undergo basal melting, providing water to cut valley networks.