African wild dogs (Lycaon pictus) occupy an ecological niche characterized by hypercarnivory and cursorial hunting. Previous interpretations drawn from a limited, mostly Eurasian fossil record suggest that the evolutionary shift to cursorial hunting preceded the emergence of hypercarnivory in the Lycaon lineage. Here we describe 1.9–1.0 ma fossils from two South African sites representing a putative ancestor of the wild dog. The holotype is a nearly complete maxilla from Coopers Cave, and another specimen tentatively assigned to the new taxon, from Gladysvale, is the most nearly complete mammalian skeleton ever described from the Sterkfontein Valley, Gauteng, South Africa. The canid represented by these fossils is larger and more robust than are any of the other fossil or extant sub-Saharan canids. Unlike other purported L. pictus ancestors, it has distinct accessory cusps on its premolars and anterior accessory cuspids on its lower premolars–a trait unique to Lycaon among living canids. However, another hallmark autapomorphy of L. pictus, the tetradactyl manus, is not found in the new species; the Gladysvale skeleton includes a large first metacarpal. Thus, the anatomy of this new early member of the Lycaon branch suggests that, contrary to previous hypotheses, dietary specialization appears to have preceded cursorial hunting in the evolution of the Lycaon lineage. We assign these specimens to the taxon Lycaon sekowei n. sp.