Living hominoids are distinguished by upright torsos and versatile locomotion. It is hypothesized that these features evolved for feeding on fruit from terminal branches in forests. To investigate the evolutionary context of hominoid adaptive origins, we analyzed multiple paleoenvironmental proxies in conjunction with hominoid fossils from the Moroto II site in Uganda. The data indicate seasonally dry woodlands with the earliest evidence of abundant C4 grasses in Africa based on a confirmed age of 21 million years ago (Ma). We demonstrate that the leaf-eating hominoid Morotopithecus consumed water-stressed vegetation, and postcrania from the site indicate ape-like locomotor adaptations. These findings suggest that the origin of hominoid locomotor versatility is associated with foraging on leaves in heterogeneous, open woodlands rather than forests.