At 8 to 15 kilometers wide, Ma'adim Vallis is one of the largest valleys in the martian highlands. Although a groundwater source was previously suggested, the channel originates at a spillway in the divide of a approximately 3,000,000-square-kilometer closed drainage basin. The interior morphology of this source basin, including likely shoreline features following topographic contours, suggests that Ma'adim Vallis was created through catastrophic overflow of a approximately 1,100,000-square-kilometer highland lake. The size, constant levels, and interior morphology of three regional paleolake basins require a warmer paleoclimate and a long-term, recharged, stable highland water table more than approximately 3.5 billion years ago.