Hyaenodonta is a diverse clade of carnivorous mammals that were part of terrestrial faunas in the Paleogene of Eurasia and North America, but the oldest record for the group is Afro-Arabian, making the record there vital for understanding the evolution of this wide-spread group. Previous studies show an ancient split between two major clades of hyaenodonts that converged in hypercarnivory: Hyainailourinae and Hyaenodontinae. These clades are each supported by cranial characters. Phylogenetic analyses of hyaenodonts also support the monophyly of Teratodontinae, an Afro-Arabian clade of mesocarnivorous to hypercarnivorous hyaenodonts. Unfortunately, the cranial anatomy of teratodontines is poorly known, and aligning the clade with other lineages has been difficult. Here, a new species of the phylogenetically controversial teratodontine Masrasector is described from Locality 41 (latest Priabonian, late Eocene) from the Fayum Depression, Egypt. The hypodigm includes the most complete remains of a Paleogene teratodontine, including largely complete crania, multiple dentaries, and isolated humeri. Standard and “tip-dating” Bayesian analyses of a character-taxon matrix that samples cranial, postcranial, and dental characters support a monophyletic Masrasector within Teratodontinae, which is consistently placed as a close sister group of Hyainailouridae. The cranial morphology of Masrasector provides new support for an expanded Hyainailouroidea (Teratodontinae + Hyainailouridae), particularly characters of the nuchal crest, palate, and basicranium. A discriminant function analysis was performed using measurements of the distal humerus from a diverse sample of extant carnivorans to infer the locomotor habits of Masrasector. Masrasector was assigned to the “terrestrial” locomotor category, a result consistent with the well-defined medial trochlear ridges, and moderately developed supinator crests of the specimens. Masrasector appears to have been a fast-moving terrestrial form with a diverse diet. These specimens considerably improve our understanding of Teratodontinae, an ancient member of the Afro-Arabian mammalian fauna, and our understanding of hyaenodont diversity before the dispersal of Carnivora to the continent near the end of the Paleogene.