The golden jackal of Africa (Canis aureus) has long been considered a conspecific of jackals distributed throughout Eurasia, with the nearest source populations in the Middle East. However, two recent reports found that mitochondrial haplotypes of some African golden jackals aligned more closely to gray wolves (Canis lupus), which is surprising given the absence of gray wolves in Africa and the phenotypic divergence between the two species. Moreover, these results imply the existence of a previously unrecognized phylogenetically distinct species despite a long history of taxonomic work on African canids. To test the distinct-species hypothesis and understand the evolutionary history that would account for this puzzling result, we analyzed extensive genomic data including mitochondrial genome sequences, sequences from 20 autosomal loci (17 introns and 3 exon segments), microsatellite loci, X- and Y-linked zinc-finger protein gene (ZFX and ZFY) sequences, and whole-genome nuclear sequences in African and Eurasian golden jackals and gray wolves. Our results provide consistent and robust evidence that populations of golden jackals from Africa and Eurasia represent distinct monophyletic lineages separated for more than one million years, sufficient to merit formal recognition as different species: C. anthus (African golden wolf) and C. aureus (Eurasian golden jackal). Using morphologic data, we demonstrate a striking morphologic similarity between East African and Eurasian golden jackals, suggesting parallelism, which may have misled taxonomists and likely reflects uniquely intense interspecific competition in the East African carnivore guild. Our study shows how ecology can confound taxonomy if interspecific competition constrains size diversification.