The Cenozoic Kalahari Basin covers large parts of southern Africa. A continuous 400 m core was obtained in northern Namibia and analyzed in detail. Here, we present sedimentological, geochemical, mineralogical, granulometric, and hydraulic data, which were used to derive the sedimentation history and the Cenozoic paleoclimate and paleogeography of SW Africa. The first absolute ages for the Kalahari Basin were obtained by dating of calcretes, which showed that the core covers almost the entire Cenozoic. Two megafans could be distinguished. The older, buried Olukonda Megafan stems from a mafic source rock, potentially the Kunene Intrusive Complex, and was deposited by a paleo–Kunene River towards the southeast and east, under a semiarid climate. The younger Cubango Megafan (Andoni Formation) has a completely different provenance, namely felsic metamorphic and granitoid rocks, transported from the north by the Cubango River. The capture of the Kunene towards the Atlantic during the Eocene resulted in this change in provenance. Despite the distinct differences between the formations, the temporal hiatus between them must have been short. The results are a showcase of the potential of megafans for hosting major deep freshwater aquifers.