Cave hyenas (genus Crocuta) were among the most representative large carnivorans of Eurasian ecosystems during the Middle-Late Pleistocene. They are close relatives of the extant African spotted hyenas, the only extant member of the genus Crocuta. However, the taxonomy of these forms is still debated. Using palaeogenetic and palaeogenomic evidence, previous studies suggested a complex evolutionary history between spotted and Eurasian cave hyenas. Up to now, no molecular data have been retrieved from their Mediterranean counterparts, leaving a gap in the understanding of population dynamics of the genus Crocuta. To investigate the relationships of the Sicilian hyena to other cave and extant spotted hyenas we obtained palaeogenomic data from a Late Pleistocene coprolite chronologically dated between 32 and 21 Ka. Surprisingly, we found that the Sicilian genome forms a basal lineage of cave hyena. Moreover, results show that the Sicilian cave hyena is less admixed with African spotted hyena than the German and Russian specimens are, thus rejecting any large scale gene flow from Africa to Sicily. Our findings show that the genetic structure of European cave hyenas was more complex than previously documented, and offers new insights into the phylogeny of the genus Crocuta.