We establish a new genus of a hyaenaelurine hyaenodontid (Creodonta: Mammalia), Orienspterodon for “Pterodon” dahkoensis, which is known from three late middle Eocene localities in central and southern China and Myanmar. This paper provides a full description of the species and a comment on the early evolution of Hyaenaelurinae. Some features of Orienspterodon (p2–p3 without an anterior accessory cuspulid, lesser reduction of the m3 talonid relative to m1–m2 talonids, double-rooted P3, and better fusion of the paracone and metacone on M1) confirm that O. dahkoensis is distinct from Pterodon. Orienspterodon differs from the other specialized hyaenodontids from the Paleogene of Asia in being a hyaenaelurine, in being unrelated to Hyaenodon, and in having a geographical distribution in the southern part of the continent. Orienspterodon represents the earliest fossil records of Hyaenaelurinae, and some features (small metaconid on m3, basined talonid on all lower molars, a short and more diagonally oriented metastyle, large size, better fused paracone and metacone) indicate an early branching of this genus from the other hyaenaelurines.