At least two classes of small valleys (subparallel slope ravines and flat-floored branching valleys) shown on Viking imagery of Mars exhibit spatial relationships to impact structures. Cessation of their formation at the terminus of the heavy bombardment period, about 3.8 Ga, also implies a causal relationship between valley formation and cratering. We hypothesize that these valley types originated through the interaction of ground ice and hot springs located along the permeable fringes of slowly cooling impact melts. The valleys grew by a combination of headward sapping and down-valley water and ice fluid flow. The probable widespread operation of impact-related hydrothermal systems early in Mars history indicates that it is not necessary to infer atmospheric changes to explain valley origin.