Delta18O values of aquatic cellulose preserved in a 7.6 m sediment core from near the center of Lake Victoria, East Africa, record a 13 000 yr hydrological history of the basin. Relative to the present value (+3.4‰), highly elevated lake-water δ18O values of +8‰ ± 2‰ from 13 200 to 7250 14C yr B.P. indicate closed-basin conditions and precipitation:evaporation ratios much smaller than at present. An abrupt drop in the lake-water δ18O to 0‰ ± 1‰ marks the rapid transition to an open basin between 7250 and 7150 14C yr B.P. From 7140 to 5400 14C yr B.P. increasing lake-water δ18O values from 0‰ ± 1‰ to +5‰ ± 1.5‰ are proposed to reflect outlet downcutting and a likely decrease in relative humidity. These data have unexpectedly shifted our view of the timing of changes in the Lake Victoria water balance and imply a period of at least 10 000 years (17 000 to 7000 14C yr B.P.) when the Lake Victoria basin did not contribute waters to the main Nile River.