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 approximate to 1475 m3 s1. Over the last 1300 years more than ten floods have exceeded 1250 m3 s1. An additional 33 floods exceeded 400 m3 s1. The last millennium was characterized by one large flood every 3040 years during the periods 12501335, 13551565 and 1715 AD to the present. A slight increase in flood frequency (not magnitude) occurred during 15651715 AD (one large flood in approximate to 20 years) and during two short episodes, 11851205 and 13351355 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. Copyright (c) 2013 John Wiley & Sons, Ltd.