Afrotheria is a newly recognized taxon comprising elephants, hyraxes, sea cows, aardvarks, golden moles, tenrecs, and elephant shrews, each of which originated in Africa. Although some members of this taxon were once classified into distantly related groups, recent molecular studies have demonstrated their close relationships. It was suggested that this group emerged as a result of physical isolation of the African continent during the successive breakup events of Gondowanaland. In this study, a novel family of SINEs, designated AfroSINEs, was isolated and characterized from the genomes of afrotherians. This SINE family is distributed exclusively among the afrotherian species, confirming their monophyletic relationships. Furthermore, a distinct subfamily, which shares a deletion in the middle region of the SINE, was identified. The distribution of this subfamily is apparently restricted to the genomes of hyraxes, elephants, and sea cows, suggesting monophyly of these three groups, which was previously proposed as Paenungulata. We characterized the structures of the AfroSINEs from all afrotherian representatives by PCR, and we discuss how they were generated as well as the phylogenetic relationships of their host species.