The assembly of Africa's iconic C4 grassland ecosystems is central to evolutionary interpretations of many mammal lineages, including hominins. C4 grasses are thought to have become ecologically dominant in Africa only after 10 million years ago (Ma). However, paleobotanical records older than 10 Ma are sparse, limiting assessment of the timing and nature of C4 biomass expansion. This study uses a multiproxy design to document vegetation structure from nine Early Miocene mammal site complexes across eastern Africa. Results demonstrate that between ~21 and 16 Ma, C4 grasses were locally abundant, contributing to heterogeneous habitats ranging from forests to wooded grasslands. These data push back the oldest evidence of C4 grass-dominated habitats in Africa-and globally-by more than 10 million years, calling for revised paleoecological interpretations of mammalian evolution.