According to molecular data, hippopotamuses and cetaceans form a clade excluding other extant cetartiodactyls. Despite a wealth of spectacular specimens documenting cetacean evolution, this relationship remains poorly substantiated by the fossil record. Indeed, the evolutionary path leading from the hippo-cetacean ancestor to Hippopotamidae is plagued by missing fossil data and phylogenetic uncertainties. Only an origination within the extinct anthracotheres is compatible with molecular results, substantial filling of phyletic gaps and recent discoveries of early Miocene hippopotamids. Yet, the anthracothere stock that gave rise to Hippopotamidae has not been identified. Consequently, recent phylogenetic accounts do not properly integrate the anthracotheriid hypothesis, and relate Hippopotamidae to a stretched ghost lineage and/or close to Suina. Here we describe a new anthracothere from Lokone (Kenya) that unambiguously roots the Hippopotamidae into a well-identified group of bothriodontines, the first large mammals to invade Africa. The hippos are deeply anchored into the African Paleogene.