The origins of Africa’s iconic C4 grassland and savanna ecosystems is key for understanding the evolution of many mammals on the continent, not least our own lineage. Current evidence from primarily pollen, biomarkers, and stable carbon isotopic data has suggested that C4 grasses became ecologically dominant in Africa only after 10 Ma. However, the paucity of paleobotanical records older than 10 Ma prevents a full evaluation of the timing and nature of C4 grass expansion. We used a multi-proxy approach, combining analyses of plant silica microfossils (phytoliths) with stable carbon isotopic data from soil organic matter, plant waxes, and pedogenic carbonates to document vegetation structure at ten Early Miocene fossil hominoid sites across eastern Africa (Kenya and Uganda). Although not every source of data was available for all sites, there is sufficient overlap at multiple sites to provide a detailed and robust view of Early Miocene vegetation. Taken together, our results demonstrate that, between 21 and 17 Ma, C4 grasses were locally abundant in vegetation at all sites, but not for every sample from those sites. This pattern points to habitat heterogeneity during the Early Miocene, ranging from closed forests to wooded grasslands, both within sites (locally) and among sites (regionally). It also pushes back the oldest fossil evidence of C4 grass-dominated habitats in Africa – and globally – by over 10 million years, suggesting that the paleoecological context for mammalian evolution in Africa, including that of hominins, needs to be reevaluated.