The aardwolf Proteles cristatus is the only known hyaenid, living or extinct, to exhibit an extremely reduced dentition related to its termite-specializing diet. The fossil record of extant aardwolves extends to 2 to 4 million years ago, but records that inform its evolutionary origins are essentially nonexistent. Such circumstance renders it difficult to place this unusual hyena in the broader evolutionary context of small-bodied hyaenid species in Eurasian Neogene deposits. Here we describe a new genus and species of a small-bodied hyaenid, Gansuyaena megalotis, representing the closest morphological link to aardwolves to date. This new fossil hyena is based on a skull with associated mandible, a rostrum preserving several teeth, and several referred specimens. The new specimens were discovered in Neogene deposits in Linxia Basin, Gansu Province, China. Phylogenetic analysis indicates that among early hyaenids, G. megalotis is most closely related, but unlikely ancestral, to the living aardwolf. Also recognized in this new species are the fossils previously referred to “Protictitherium” aff. P. gaillardi from Pasalar, Turkey. Additionally, “Plioviverrops” guerini from Los Mansuetos, Spain is interpreted to represent a second Gansuyaena species. In addition to the living aardwolf, Proteles cristatus, our analyses suggest that the proteline lineage includes the extinct genera Gansuyaena, Mesoviverrops, and Plioviverrops. Although the precise timing and geographic location of evolutionary divergence between the aardwolf and Gansuyaena remain elusive, critical new morphological information provided by Gansuyaena specimens reinforce findings from recent genomic analyses that the aardwolf lineage has an ancient origin from small-bodied stem hyaenids prior to the appearance of large and robust bone-cracking hyaenines.