Gullies on Mars resemble water-carved channels on Earth, but they are mostly at elevations where liquid water is not expected under current climate conditions. It has been suggested that sublimation of carbon dioxide ice alone could have formed Martian gullies. We used a general circulation model to show that the highest-elevation Martian gullies coincide with the boundary of terrain that experienced pressures above the triple point of water when Mars' rotational axis tilt reached 35°. Those conditions have occurred repeatedly over the past several million years, most recently ~630,000 years ago. Surface water ice, if present at these locations, could have melted when temperatures rose >273 kelvin. We propose a dual gully formation scenario that is driven by melting of water ice followed by carbon dioxide ice sublimation.