Interannual rainfall variations in equatorial East Africa are tightly linked to the El Niño Southern Oscillation (ENSO), with more rain and flooding during El Niño and droughts in La Niña years, both having severe impacts on human habitation and food security. Here we report evidence from an annually laminated lake sediment record from southeastern Kenya for interannual to centennial-scale changes in ENSO-related rainfall variability during the last three millennia and for reductions in both the mean rate and the variability of rainfall in East Africa during the Last Glacial period. Climate model simulations support forward extrapolation from these lake sediment data that future warming will intensify the interannual variability of East Africa's rainfall.