Cenozoic uplift of the East African Plateau has been associated with fundamental climatic and environmental changes in East Africa and adjacent regions. While this influence is widely accepted, the timing and the magnitude of plateau uplift have remained unclear. This uncertainty stems from the lack of datable, geomorphically meaningful reference horizons that could record surface uplift. Here, we document the existence of significant relief along the East African Plateau prior to rifting, as inferred from modeling the emplacement history of one of the longest terrestrial lava flows, the ∼300-km-long Yatta phonolite flow in Kenya. This 13.5 Ma lava flow originated on the present-day eastern Kenya Rift flank, and utilized a riverbed that once routed runoff from the eastern rim of the plateau. Combining an empirical viscosity model with subsequent cooling and using the Yatta lava flow geometry and underlying paleotopography (slope angle), we found that the prerift slope was at least 0.2°, suggesting that the lava flow originated at a minimum elevation of 1400 m. Hence, high paleotopography in the Kenya Rift region must have existed by at least 13.5 Ma. We infer from this that middle Miocene uplift occurred, which coincides with the two-step expansion of grasslands, as well as important radiation and speciation events in tropical Africa.