The Turkana Depression of northern Kenya and southern Ethiopia contains voluminous plume-related basalts that mark the onset of the Paleogene–recent East African Rift System (EARS) at ca. 45 Ma. Thus, the Turkana Depression is crucial to understanding the inception of intracontinental rifting. However, the precise chronology of early rift-basin formation in Turkana is poorly constrained. We present apatite fission-track and (U-Th-Sm)/He thermochronology data from basement rocks from the margins of the north-south–trending Lokichar Basin that constrain the onset of rift-related cooling. Thermal history modeling of these data documents pronounced Eocene to Miocene denudational cooling of the basin-bounding Lokichar fault footwall. These results, along with ∼7 km of Paleogene to middle Miocene syn-rift strata preserved in the Lokichar fault hanging wall, suggest that formation of the Lokichar Basin began as early as ca. 45–40 Ma. Preexisting lithospheric heterogeneities inherited from earlier Mesozoic rifting and Eocene plume magmatism likely facilitated the broadly concurrent nucleation of strain in the Turkana Depression, up to ∼15 m.y. earlier than EARS initiation elsewhere. Late Paleogene extension in the Lokichar Basin and other parts of Turkana significantly predate the Miocene creation of pronounced plume-related topography in East Africa, suggesting that other mechanism(s), such as far-field stresses or mantle basal drag, likely played a critical role during EARS inception.