The tephrostratigraphic framework for Pliocene and Early Pleistocene paleoanthropological sites in East Africa has been well established through nearly 50 years of research, but a similarly comprehensive framework is lacking for the Middle and particularly the Late Pleistocene. We provide the first detailed regional record of Late Pleistocene tephra deposits associated with artifacts or fossils from the Lake Victoria basin of western Kenya. Correlations of Late Pleistocene distal tephra deposits from the Wasiriya beds on Rusinga Island, the Waware beds on Mfangano Island and deposits near Karungu, mainland Kenya, are based on field stratigraphy coupled with 916 electron microprobe analyses of eleven major and minor element oxides from 50 samples. At least eight distinct distal tephra deposits are distinguished, four of which are found at multiple localities spanning >60 km over an approximately north to south transect. New optically stimulated luminescence dates help to constrain the Late Pleistocene depositional ages of these deposits. Our correlation and characterization of volcaniclastic deposits expand and refine the current stratigraphy of the eastern Lake Victoria basin. This provides the basis for relating fossil- and artifact-bearing sediments and a framework for ongoing geological, archaeological and paleontological studies of Late Pleistocene East Africa, a crucial time period for human evolution and dispersal within and out of Africa.