Reconstruction of lake-water δ18O from analysis of cellulose δ18O in two sediment cores from Lake Victoria, East Africa, shows a large shift to lower values during the terminal Pleistocene. This shift records the transition from closed- to open-basin conditions following desiccation at the Last Glacial Maximum. Although oxygen isotope analysis of cellulose from one core had placed this overflow at 8 ka (7200 14C yr B.P.), reevaluation of the age model for this core, in addition to new stratigraphic and chronological evidence from a second core, suggests that basin overflow was established much earlier, ca. 13 ka. Our refined view of the timing of Lake Victoria overflow inferred from the oxygen isotope records is consistent with other paleolimnological studies, indicating that lake-sediment cellulose is an effective and sensitive isotopic archive of major hydrologic events in this region.