Since the discovery of the megaherbivore Arsinoitherium zitteli Beadnell (early Oligocene of Egypt), the extinct order Embrithopoda has remained an enigmatic group, with disputed affinities among ungulates. In this study, new specimens of Palaeoamasia kansui from the early Palaeogene of Turkey are described and a synthetic dental terminology is proposed for embrithopods. Based on 130 cranial–mandibular and dental characters, the first phylogenetic analysis of embrithopods is carried out in aim to enhance the position of Palaeoamasia within embrithopods. The monophyly of Embrithopoda is confirmed, following the topology (Phenacolophus (Namatherium (Arsinoitheriinae, Palaeamasiinae))). However, phylogenetic relationships between Eurasian embrithopods (Palaeoamasiinae: Palaeoamasia, Crivadiatherium and Hypsamasia) remain unresolved. The integration of all embrithopod genera within a cladistic analysis encompassing a wider taxonomic sample (Condylarthra, Afrotheria/Paenungulata and Laurasiatheria) also supports Embrithopoda as being monophyletic, but questions the position of both Phenacolophus and Namatherium within Embrithopoda. Finally, possible faunal exchange events are proposed based on three hypothesized scenarios between Eurasia and Arabia–Africa during the early Palaeogene.