New information about the early cercopithecoids Prohylobates tandyi (Wadi Moghra, Egypt) and Prohylobates sp. indet. (Buluk and Nabwal, Kenya) is presented. Comparisons are made among all major collections of Early and Middle Miocene catarrhine monkeys, and a systematic revision of the early Old World monkeys is provided. Previous work involving the systematics of early Old World monkeys (Victoriapithecidae; Cercopithecoidea) has been hampered by a number of factors, including the poor preservation of Prohylobates material from North Africa and lack of comparable anatomical parts across collections. However, it is now shown that basal cercopithecoid species from both northern and eastern Africa can be distinguished from one another on the basis of degree of lower molar bilophodonty, relative lower molar size, occlusal details, symphyseal construction, and mandibular shape. Results of particular interest include: 1) the first identification of features that unambiguously define Prohylobates relative to Victoriapithecus; 2) confirmation that P. tandyi is incompletely bilophodont; and 3) recognition of additional victoriapithecid species.