Abstract: Early Mars had rivers, but the cause of Mars' wet-to-dry transition remains unknown. Past climate on Mars can be probed using the spatial distribution of climate-sensitive landforms. We analyzed global databases of water-worked landforms and identified changes in the spatial distribution of rivers over time. These changes are simply explained by comparison to a simplified meltwater model driven by an ensemble of global climate model simulations, as the result of $\gtrsim$10 K global cooling, from global average surface temperature (T) $\ge$ 268 K to T $\sim$ 258 K, due to a weaker greenhouse effect. In other words, river-forming climates on Early Mars were warm and wet first, and cold and wet later. Surprisingly, analysis of the greenhouse effect within our ensemble of global climate model simulations suggests that this shift was primarily driven by waning non-CO2 radiative forcing, and not changes in CO2 radiative forcing.