The African Hyaenodontida, mainly known from the Late Eocene and Early Oligocene Fayum depression in Egypt, show a very poor diversity in oldest Paleogene localities. Here we report new hyaenodontidans found in the late Middle Eocene deposits of Dur At-Talah (Central Libya), known to have recorded the earliest radiation of African anthropoids. The new hyaenodontidan remains are represented by dental and postcranial specimens comprising the historical material discovered by R.J.G. Savage in the last century and that of the recent Franco-Libyan campaigns. This material includes two apterodontines, in particular a subcomplete skeleton of Apterodon langebadreae nov. sp., bringing new postcranial elements to the fossil record of the genus Apterodon. Anatomical analysis of the postcranial remains of Dur At-Talah suggests a semi-aquatic lifestyle for Apterodon, a completely unusual locomotion pattern among hyaenodontidans. We also perform the first cladistic analysis of hyaenodontidans including apterodontines: Apterodon and Quasiapterodon appear close relatives to "hyainailourines", in particular to the African Oligo-Miocene Metasinopa species. Apterodon langebadreae nov. sp. could be the most primitive species of the genus, confirming an African origin of the Apterodontinae and a further dispersion event to Europe before the early Oligocene. These data enhance our knowledge of early hyaenodontidan diversification into Africa and underline how crucial is the understanding of their evolutionary history for the improvement of Paleogene paleobiogeographic scenarii.