Molecular-based analyses showed that extant " ungulate " mammals are polyphyletic and belong to the two main clades Afrotheria (Paenungulata) and Laurasiatheria (Euungulata: Cetartiodactyla-Perissodactyla). However, paleontological and neontological studies hitherto failed to demonstrate the morphological convergence of African and Laurasian " ungulate " orders. They support an " Altungulata " group including the Laurasian order Perissodactyla and the African superorder Paenungulata and characterized especially by quadritubercular and bilophodont molars adapted for a folivorous diet. We report new critical fossils of one of the few known African condylarth-like mammal, the enigmatic Abdounodus from the middle Paleocene of Morocco. They show that Abdounodus and Ocepeia display key intermediate morphologies refuting the homology of the fourth main cusp of upper molars in Paenungulata and Perissodactyla: Paenungulates unexpectedly have a metaconule-derived pseudohypo-cone, instead of a cingular hypocone. Comparative and functional dental anatomy of Abdou-nodus demonstrates indeed the convergence of the quadritubercular and bilophodont pattern in " ungulates ". Consistently with our reconstruction of the structural evolution of paenungulate bilophodonty, the phylogenetic analysis relates Abdounodus and Ocepeia to Paenungulata as stem taxa of the more inclusive new clade Paenungulatomorpha which is distinct from the Perissodactyla and Anthracobunidae. Abdounodus and Ocepeia help to identify the first convincing synapomorphy within the Afrotheria–i.e., the pseudohypocone–that demonstrates the morphological convergence of African and Laurasian ungulate-like placentals, in agreement with molecular phylogeny. Abdounodus and Ocepeia are the only known representatives of the early African ungulate radiation predating the divergence of extant paenungulate orders. Paenungulatomorpha evolved in Africa since the early Tertiary independently from laura-siatherian euungulates and " condylarths " such as apheliscids. The rapid early Tertiary radiation of the Afrotheria and Paenungulatomorpha, as illustrated by the Paleocene Moroccan mammals, is concurrent with that of the Laurasiatheria in a general, explosive mammal evolution in both the South and North Tethyan continents following the K/Pg event.