It is widely understood that Hominoidea (apes and humans) and Cercopithecoidea (Old World monkeys) have a common ancestry as Catarrhini deeply rooted in Afro-Arabia. The oldest stem Catarrhini in the fossil record are Propliopithecoidea, known from the late Eocene to early Oligocene epochs (roughly 35-30 Myr ago) of Egypt, Oman and possibly Angola. Genome-based estimates for divergence of hominoids and cercopithecoids range into the early Oligocene; however, the mid-to-late Oligocene interval from 30 to 23 Myr ago has yielded little fossil evidence documenting the morphology of the last common ancestor of hominoids and cercopithecoids, the timing of their divergence, or the relationship of early stem and crown catarrhines. Here we describe the partial cranium of a new medium-sized (about 15-20 kg) fossil catarrhine, Saadanius hijazensis, dated to 29-28 Myr ago. Comparative anatomy and cladistic analysis shows that Saadanius is an advanced stem catarrhine close to the base of the hominoid-cercopithecoid clade. Saadanius is important for assessing competing hypotheses about the ancestral morphotype for crown catarrhines, early catarrhine phylogeny and the age of hominoid-cercopithecoid divergence. Saadanius has a tubular ectotympanic but lacks synapomorphies of either group of crown Catarrhini, and we infer that the hominoid-cercopithecoid split happened later, between 29-28 and 24 Myr ago.