Recent comprehensive studies of DNA sequences support the monophyly of Afrotheria, comprising elephants, sirenians (dugongs and manatees), hyraxes, tenrecs, golden moles, aardvarks, and elephant shrews, as well as that of Paenungulata, comprising elephants, sirenians, and hyraxes. However, phylogenetic relationships among paenungulates, as well as among nonpaenungulates, have remained ambiguous. Here we applied an extensive retroposon analysis to these problems to support the monophyly of aardvarks, tenrecs, and golden moles, with elephant shrews as their sister group. Regarding phylogenetic relationships in Paenungulata, we could characterize only one informative locus, although we could isolate many insertions specific to each of three lineages, namely, Proboscidea, Sirenia, and Hyracoidea. These data prompted us to reexamine phylogenetic relationships among Paenungulata using 19 nuclear gene sequences resulting in three different analyses, namely, short interspersed element (SINE) insertions, nuclear sequence analyses, and morphological cladistics, supporting different respective phylogenies. We concluded that these three lineages diverged very rapidly in a very short evolutionary period, with the consequence that ancestral polymorphism present in the last common ancestor of Paenungulata results in such incongruence. Our results suggest the rapid fixation of many large-scale morphological synapomorphies for Tethytheria; implications of this in relation to the morphological evolution in Paenungulata are discussed.