The largest Kuiseb River floods initiate at the basin's semi-arid headwater. Downstream, along the hyperarid Namib Desert, these floodwaters are feeding shallow alluvial aquifers, the only available water for human activity and for the natural ecology. Here, we characterize the largest floods and their changing frequency and magnitudes using palaeohydrological methods. Along 120km of the rivers canyon 35 palaeoflood deposit sites were identified. At five of these sites we conducted stratigraphic and geochronological analyses and flood discharge estimations. The upper bound of the largest flood over the late Holocene is ∼1475 m3s-1. Over the last 1300 years more than ten floods have exceeded 1250 m3s-1. An additional 33 floods exceeded 400 m3s-1. The last millennium was characterized by one large flood every 30-40 years during the periods 1250-1335, 1355-1565 and 1715 AD to the present. A slight increase in flood frequency (not magnitude) occurred during 1565-1715 AD (one large flood in ∼20 years) and during two short episodes, 1185-1205 and 1335-1355 AD (seven and four floods in 20 years, respectively). These episodes of increased flood frequency are associated with other proxy records of higher water availability in the Namib. © 2013 John Wiley & Sons, Ltd.