Evidence for Quaternary climate change in East Africa has been derived from outcrops on land and lake cores and from marine dust, leaf wax, and pollen records. These data have previously been used to evaluate the impact of climate change on hominin evolution, but correlations have proved to be difficult, given poor data continuity and the great distances between marine cores and terrestrial basins where fossil evidence is located. Here, we present continental coring evidence for progressive aridification since about 575 thousand years before present (ka), based on Lake Magadi (Kenya) sediments. This long-term drying trend was interrupted by many wet-dry cycles, with the greatest variability developing during times of high eccentricity-modulated precession. Intense aridification apparent in the Magadi record took place between 525 and 400 ka, with relatively persistent arid conditions after 350 ka and through to the present. Arid conditions in the Magadi Basin coincide with the Mid-Brunhes Event and overlap with mammalian extinctions in the South Kenya Rift between 500 and 400 ka. The 525 to 400 ka arid phase developed in the South Kenya Rift between the period when the last Acheulean tools are reported (at about 500 ka) and before the appearance of Middle Stone Age artifacts (by about 320 ka). Our data suggest that increasing Middle- to Late-Pleistocene aridification and environmental variability may have been drivers in the physical and cultural evolution of Homo sapiens in East Africa.