Reconstructing hydrological variability is critical for understanding Lake Victoria’s ecosystem history, the evolution of its diverse endemic fish community, the dynamics of vegetation in the catchment, and the dispersal of aquatic and terrestrial fauna in the East African Rift system during Latest Pleistocene and Holocene times. Whereas consensus exists on widespread desiccation of Lake Victoria ∼18 – 17 ka, the re-filling history (16 – 13 ka) has remained highly controversial. Here, we present data from four new sediment cores along a depth transect. We use lithostratigraphic core correlation, sediment facies, XRF data, wetland vegetation analysis (Typha pollen), and ¹⁴C chronologies of unprecedented precision to document Latest Pleistocene lake-level variability. At our coring site in the central basin, local Typha wetlands existed >16.7 ka, alternating with periods of desiccation. Moisture increased slightly between ca. 16.7 – 14.5 ka and wetlands with permanent, shallow ponds established simultaneously in the center and the marginal, more elevated parts of the flat lake basin. After ca. 14.0 ka, lake levels increased; wetlands in the central basin were submerged and replaced by lacustrine environments and a >50 m deep lake established ca. 13.5 ka, likely with intermittent overflow most of the time. The lake reached modern or even above-modern levels around 10.8 ka. This lake-level history is consistent with regional terrestrial paleoenvironmental reconstructions, notably the expansion of Afromontane and rainforest. Our data suggest a complex picture of paleoclimatic conditions in Eastern Africa and teleconnections to the North-Atlantic and Indian Ocean domains.