The last half-million years of geological history of the East African Rift in southern Kenya is recorded by the Oltulelei Formation, which is newly described in this paper. Well-dated depositional cycles in this formation reveal how tectonics and climate shaped rift valley sedimentation, as well as the landscapes inhabited by human ancestors. The Oltulelei Formation (ca. 320 to ca. 36 ka) overlies the Olorgesailie Formation (1.2–0.5 Ma) on an erosional unconformity and is divided into three successive units, the Olkesiteti, Oltepesi, and Tinga Members. The stratotype for the formation is exposed in the Olorgesailie Basin, north and northwest of Mount Olorgesailie. The 40Ar/39Ar dates on interbedded tephras provide geochronological controls on the timing of three major depositional cycles. Lateral variability in the Oltulelei Formation shows that the Olorgesailie Basin and the northern Koora Graben formed three rift subbasins that were periodically connected and disconnected over the past 500 k.y. Erosional phases removed large volumes of sediment from the Olorgesailie Basin, requiring through-flowing drainage to a lower base level southwest and south of Mount Olorgesailie. Aggradational phases were primarily fluvial, with siliciclastic and volcaniclastic sediment filling valleys and burying dissected landscapes. Tufa, shallow lacustrine, and wetlands deposits also occur and indicate elevated water tables in fault-controlled sumps or blocked drainages. We propose that connections and disconnections between rift segments were driven by tectonic forces, primarily faulting of volcanic basement rocks and periodic influxes of volcanic sediment, combined with climatic conditions that enabled erosion and transport of large volumes of sediment into and out of the subbasins. The Oltulelei Formation preserves a record of a dynamic change in the physical landscape of the southern Kenya Rift, with major shifts in erosion versus deposition on time scales of 104–105 yr. This study provides new, well-calibrated information on sedimentation in active rift settings as well as an outcrop-based, three-dimensional, basin-scale geological history that can be integrated with emerging drill-core paleoclimate records from southern Kenya. The stratigraphic record preserved in the Oltulelei Formation advances understanding and poses new questions about how tectonics and climate shaped middle to late Pleistocene faunal turnover and the transition in southern Kenya from Acheulean to Middle Stone Age technology.