Throughout the Paleogene, most terrestrial carnivore niches in Afro-Arabia were occupied by Hyaenodonta, an extinct lineage of placental mammals. By the end of the Miocene, terrestrial carnivore niches had shifted to members of Carnivora, a clade with Eurasian origins. The transition from a hyaenodont-carnivore fauna to a carnivoran-carnivore fauna coincides with other ecological changes in Afro-Arabia as tectonic conditions in the African Rift System altered climatic conditions and facilitated faunal exchange with Eurasia. Fossil bearing deposits in the Nsungwe Formation in southwestern Tanzania are precisely dated to ~25.2 Ma (late Oligocene), preserving a late Paleogene Afro-Arabian fauna on the brink of environmental transition, including the earliest fossil evidence of the split between Old World monkeys and apes. Here we describe a new hyaenodont from the Nsungwe Formation, Pakakali rukwaensis gen. et sp. nov., a bobcat-sized taxon known from a portion of the maxilla that preserves a deciduous third premolar and alveoli of dP4 and M1. The crown of dP3 bears an elongate parastyle and metastyle and a small, blade-like metacone. Based on alveolar morphology, the two more distal teeth successively increased in size and had relatively large protocones. Using a hyaenodont character-taxon matrix that includes deciduous dental characters, Bayesian phylogenetic methods resolve Pakakali within the clade Hyainailouroidea. A Bayesian biogeographic analysis of phylogenetic results resolve the Pakakali clade as Afro-Arabian in origin, demonstrating that this small carnivorous mammal was part of an endemic Afro-Arabian lineage that persisted into the Miocene. Notably, Pakakali is in the size range of carnivoran forms that arrived and began to diversify in the region by the early Miocene. The description of Pakakali is important for exploring hyaenodont ontogeny and potential influences of Afro-Arabian tectonic events upon mammalian evolution, providing a deep time perspective on the stability of terrestrial carnivore niches through time.