The genus Crocuta (African spotted and Eurasian cave hyenas) includes several closely related extinct and extant lineages. The relationships among these lineages, however, are contentious. Through the generation of population-level paleogenomes from late Pleistocene Eurasian cave hyena and genomes from modern African spotted hyena, we reveal the cross-continental evolutionary relationships between these enigmatic hyena lineages. We find a deep divergence (~2.5 Ma) between African and Eurasian Crocuta populations, suggesting that ancestral Crocuta left Africa around the same time as early Homo. Moreover, we find discordance between nuclear and mitochondrial phylogenies and evidence for bidirectional gene flow between African and Eurasian Crocuta after the lineages split, which may have complicated prior taxonomic classifications. Last, we find a number of introgressed loci that attained high frequencies within the recipient lineage, suggesting some level of adaptive advantage from admixture.