Liquid water is not currently stable on the surface of Mars, but images provided by the Mars Orbiter Camera aboard the Mars Global Surveyor spacecraft reveal erosional landforms previously interpreted to be geologically young gullies formed by groundwater seepage. We test the basic hypothesis that, as on Earth, the location of these gullies is controlled in part by the presence of an impermeable rock layer (aquiclude) and that the depths of the gully heads below the surface should thus be correlated to subsurface geology. We show that (1) gullies emanate from a specific cliff-forming layer, even if the layer is faulted, and (2) the depth of gullies below the local surface ranges from 70 to 800 m, and (3) is positively correlated to mapped geologic units. Gully formation is therefore dependent upon both favorable climatic conditions to produce and sustain liquid water and the presence of impermeable subsurface layers to collect the groundwater. Gullies may mark the distribution of subsurface impermeable layers globally, and are prime targets for the search for present water and life on Mars.