Recent palaeontological surveys in Early Miocene sediments at Napak (Uganda), Koru (Kenya) and Grillental (Namibia) have resulted in the collection of a number of small to medium-sized hyaenodonts and carnivorans, some of which were poorly represented in previous collections. The present article describes and interprets the hyaenodonts from these localities. The new fossils permit more accurate interpretation of some of the poorly known taxa, but new taxa are also present. The fossils reveal the presence of a hitherto unsuspected morphofunctional dentognathic system in the Hyaenodontidae which is described and defined, along with previously documented dentognathic complexes. Two new tribes, three new genera and one new species are diagnosed. Keywords: Hyaenailurinae, Hyaenodonta, Creodonta, Systematics, Miocene, Africa.