Amphitheater-headed valleys are common on the surfaces of Earth and Mars. The abrupt terminations of these valleys at their headwalls have been used extensively to argue for valley erosion from springs (i.e., seepage erosion or groundwater sapping) rather than surface runoff. This interpretation has significant implications for Martian hydrology and the associated prospects for life. A connection between channel form and the erosion processes induced by groundwater, however, has not been demonstrated in resistant rock. Perhaps the most widely cited terrestrial analogs for Martian amphitheater-headed valleys in basalt are the spectacular canyons of Kohala, Hawai‘i. Here we present new field observations and topographic analyses of the amphitheater-headed Kohala valleys. We found no evidence for intensively weathered rocks or alcoves around springs at valley headwalls. Instead, valley-head erosion appears to be dominated by waterfall plunge pools. Stream flow from peak annual precipitation events exceeds spring discharge by more than an order of magnitude, and such flow is responsible for evacuation of the coarse sediment that lines the streams. Bathymetric surveys along the Kohala coast have revealed a large submarine landslide, the Pololū Slump, directly offshore of the Kohala valleys. We propose that the headscarp of this massive landslide is expressed as the present-day ∼400 m Kohala sea cliffs. As dominant streams poured over this headscarp as waterfalls, vertical plunge pool erosion and undercutting caused upstream propagation of knickpoints, eventually producing amphitheater-headed valleys. Island subsidence rates and the ages of volcanic eruptions and submarine terraces indicate that the average rate of valley headwall advance is as high as 60 mm/yr. We propose a simple expression for upslope headwall propagation by vertical waterfall erosion based on abrasion by impacting sediment particles in plunge pools. This model indicates that head-wall propagation depends nonlinearly on the sediment flux passing over the waterfall and linearly on the ratio of kinetic versus potential energy of sediment impacts. After the Pololū Slump, many streams did not form upslope-propagating waterfalls because they had smaller discharges due to a radial drainage pattern and fault-bounded drainage divides, which prevented runoff from the wetter summit of the volcano. A threshold for headwall propagation due to sediment supply or sediment-transport capacity is consistent with the model. Island subsidence following valley formation has resulted in alluviation of the valley floors, which has created the observed U-shaped valley cross sections. Our interpretation implies that surface runoff can carve amphitheater-headed valleys and that seepage erosion cannot be inferred based solely on valley form on Earth, Mars, or other planets.