The origin of gullies on Mars is controversial (e.g., catastrophic groundwater release, debris flows, dry granular flows, or meltwater from surface ice and snow) and their ages are difficult to determine due to their small size. We describe a gully depositional fan that contains a unique chronostratigraphic marker (secondary crater clusters) between episodes of gully activity during fan development. This marker can be traced to its source, a 7-km-diameter rayed crater that we have dated as ca. 1.25 Ma. This age links gully activity to the emplacement of dust-ice mantling deposits interpreted to represent recent ice ages on Mars. This association, together with multiple episodes of depositional fan formation, favors an origin for these gullies from top-down melting of snow and ice during multiple favorable spin-axis and orbital variations. This melting mechanism is consistent with the occurrence of gullies in unique steep-sloped, poleward-facing insolation microenvironments that favor the melting of small amounts of surficial snow and ice.