Geomorphic evidence suggests that recent gullies on Mars were formed by fluvial activity. The Martian gully features are significant because their existence implies the presence of liquid water near the surface on Mars in geologically recent times. Irrespective of the ultimate source of the fluid carving the gullies, we seek to understand the behavior of this fluid after it reaches the Martian surface. We find that contrary to popular belief, the fluvially carved Martian gullies are consistent with formation conditions such as now occur on Mars, outside of the temperature-pressure stability regime of liquid water. Our model of the action of flowing pure liquid water produces the observed gully length distribution only at surface pressures and temperatures below the triple point where liquid water simultaneously boils and freezes and thus suggests that gullies were formed under conditions similar to present-day Mars. Our results suggest a typical flow rate of 30 m3/s to carve the gully channels. At least 0.15 km3 has flowed across the surface of Mars to carve the gully systems observed today, and this would require an aquifer recharge rate of ~10-13--10-12 m/yr. The absence of gullies on Mars that are long enough to have been created above the triple point pressure argues that the atmospheric pressure has not been significantly larger than it is now since the origin of the gullies. This result may imply that Mars does not possess a significant reservoir of condensed CO2.