The mammalian order Xenarthra (armadillos, anteaters and sloths) is one of the four major clades of placentals, but it remains poorly studied from the molecular phylogenetics perspective. We present here a study encompassing most of the order's diversity in order to establish xenarthrans' intra–ordinal relationships, discuss the evolution of their morphological characters, search for their extant sister group and specify the timing of their radiation with special emphasis on the status of the controversial fossil Eurotamandua. Sequences of three genes (nuclear exon 28 of the Von Willebrand factor and mitochondrial 12S and 16S rRNAs) are compared for eight of the 13 living genera. Phylogenetic analyses confirm the order's monophyly and that of its three major lineages: armadillos (Cingulata), anteaters (Vermilingua) and sloths (‘Tardigrada’, renamed in ‘Folivora’), and our results strongly support the grouping of hairy xenarthrans (anteaters and sloths) into Pilosa. Within placentals, Afrotheria might be the first lineage to branch off, followed by Xenarthra. The morphological adaptative convergence between New World xenarthrans and Old World pangolins is confirmed. Molecular datings place the early emergence of armadillos around the Cretaceous/Tertiary boundary, followed by the divergence between anteaters and sloths in the Early Eocene era. These Tertiary dates contradict the concept of a very ancient origin of modern xenarthran lineages. They also question the placement of the purported fossil anteater (Eurotamandua) from the Middle Eocene period of Europe with the Vermilingua and instead suggest the independent and convergent evolution of this enigmatic taxon.