Modern mammals rapidly evolved in the early Cenozoic in all continental provinces, including in Africa, with one of the first placental branches, the Afrotheria [1, 2]. Afrotherian evolution is at the origin of the major radiation of African ungulate-like mammals, including extant hyrax, elephant, and sea cow orders, which all belong to the Paenungulata. The paenungulate radiation also includes the extinct order Embrithopoda of uncertain interordinal relationships, which is best known for the giant and strangely specialized Oligocene genus Arsinoitherium. The Ouled Abdoun basin, Morocco, yielded exceptional Paleocene-Eocene fossils documenting the early paenungulate evolution [3, 4, 5, 6, 7, 8]. Here we report two new small Ypresian species, Stylolophus minor n.g., n.sp. and cf. Stylolophus sp., which are the earliest and most primitive embrithopods. The cladistic analysis relates the Embrithopoda to crown paenungulates as the stem-group of the Tethytheria, which makes crown tethytherians restricted to extant elephant and sea cow orders. The Embrithopoda is therefore an early tethytherian offshoot predating the elephant and sea cow divergence. The resulting phylogeny supports a strictly African early radiation of the paenungulates excluding the Phenacolophidae and Anthracobunia. It sustains an at least early Paleocene African origin of the Embrithopoda. The unique tooth pattern of the embrithopods (hyperdilambdodont and pseudolophodont molars) is resolved as evolving early and directly from the dilambdodont (W-shaped labial molar crests) ancestral paenungulate morphotype. The specialized upper molar morphology with two transverse crests is convergent and non-homologous in embrithopods and crown Tethytheria. These convergences for specialized folivorous diet were driven by free herbivorous African niches in the early Paleogene.