Ma'adim Vallis, one of the largest valleys in the Martian highlands, appears to have originated by catastrophic overflow of a large paleolake located south of the valley heads. Ma'adim Vallis debouched to Gusev crater, 900 km to the north, the landing site for the Spirit Mars Exploration Rover. Support for the paleolake overflow hypothesis comes from the following characteristics: (1) With a channel width of 3 km at its head, Ma'adim Vallis originates at two (eastern and western) gaps incised into the divide of the ∼1.1 M km2 enclosed Eridania head basin, which suggests a lake as the water source. (2) The sinuous course of Ma'adim Vallis is consistent with overland flow controlled by preexisting surface topography, and structural control is not evident or required to explain the valley course. (3) The nearly constant ∼5 km width of the inner channel through crater rim breaches, the anastomosing course of the wide western tributary, the migration of the inner channel to the outer margins of bends in the valley's lower reach, a medial sedimentary bar ∼200 m in height, and a step-pool sequence are consistent with modeled flows of 1–5 × 106 m3/s. Peak discharges were likely higher but are poorly constrained by the relict channel geometry. (4) Small direct tributary valleys to Ma'adim Vallis have convex-up longitudinal profiles, suggesting a hanging relationship to a valley that was incised quickly relative to the timescales of tributary development. (5) The Eridania basin had adequate volume between the initial divide and the incised gap elevations to carve Ma'adim Vallis during a single flood. (6) The Eridania basin is composed of many overlapping, highly degraded and deeply buried impact craters. The floor materials of the six largest craters have an unusually high internal relief (∼1 km) and slope (∼0.5–1.5°) among degraded Martian craters, which are usually flat-floored. Long-term, fluvial sediment transport appears to have been inhibited within these craters, and the topography is inconsistent with basaltic infilling. (7) Fluvial valleys do not dissect the slopes of these deeper crater floor depressions, unlike similar slopes that are dissected at higher levels in the watershed. These characteristics (6, 7) suggest that water mantled at least the lower parts of the Eridania basin floor throughout the period of relatively intense erosion early in Martian history. The lake level increased and an overflow occurred near the close of the Noachian (age determined using >5 km crater counts). Initially, the Eridania basin debouched northward at two locations into the intermediate basin, a highly degraded impact crater ∼500 km in diameter. As this intermediate basin was temporarily filled with water, erosion took place first along the lower (northern) reach of Ma'adim Vallis, debouching to Gusev crater. The western overflow point was later abandoned, and erosion of the intermediate basin interior was concentrated along the eastern pathway. Subsequent air fall deposition, impact gardening, tectonism, and limited fluvial erosion modified the Eridania basin region, so evidence for a paleolake is restricted to larger landforms that could survive post-Noachian degradation processes.