Extant African great apes and humans are thought to have diverged from each other in the Late Miocene. However, few hominoid fossils are known from Africa during this period. Here we describe a new genus of great ape (Nakalipithecus nakayamai gen. et sp. nov.) recently discovered from the early Late Miocene of Nakali, Kenya. The new genus resembles Ouranopithecus macedoniensis (9.6-8.7 Ma, Greece) in size and some features but retains less specialized characters, such as less inflated cusps and better-developed cingula on cheek teeth, and it was recovered from a slightly older age (9.9-9.8 Ma). Although the affinity of Ouranopithecus to the extant African apes and humans has often been inferred, the former is known only from southeastern Europe. The discovery of N. nakayamai in East Africa, therefore, provides new evidence on the origins of African great apes and humans. N. nakayamai could be close to the last common ancestor of the extant African apes and humans. In addition, the associated primate fauna from Nakali shows that hominoids and other non-cercopithecoid catarrhines retained higher diversity into the early Late Miocene in East Africa than previously recognized.