The Early Miocene Napak XV locality (ca 20.5 Ma), Uganda, has yielded an interesting assemblage of fossils, including the very well represented amphicyonid Hecubides euryodon. The remarkable find of a nearly complete mandible, unfortunately with poorly preserved dentition, together with new dental remains allow us to obtain a better idea about the morphology and variability of this species. Additionally, we describe a newly discovered mandible of Hecubides euryodon from the Grillental-VI locality (Sperrgebiet, Namibia), which is the most complete and diagnostic Amphicyonidae material found in this area. Comparisons with Cynelos lemanensis from Saint-Gérand-le-Puy (France), the type locality, and with an updated sample of the species of amphicyonids described in Africa leads us to validate the genus Hecubides. Hecubides would be phylogenetically related to the medium and large size species of Amphicyonidae from Africa, most of them now grouped into the genera Afrocyon and Myacyon, both endemic to this continent. Keywords: Carnivora, Amphicyonidae, Miocene, Africa, Systematics.