The living Malagasy lemurs constitute a spectacular radiation of >50 species that are believed to have evolved from a common ancestor that colonized Madagascar in the early Tertiary period. Yet, at least 15 additional Malagasy primate species, some of which were relative giants, succumbed to extinction within the past 2,000 years. Their existence in Madagascar is recorded predominantly in its Holocene subfossil record. To rigorously test the hypothesis that all endemic Malagasy primates constitute a monophyletic group and to determine the evolutionary relationships among living and extinct taxa, we have conducted an ancient DNA analysis of subfossil species. A total of nine subfossil individuals from the extinct genera Palaeopropithecus and Megaladapis yielded amplifiable DNA. Phylogenetic analysis of cytochrome b sequences derived from these subfossils corroborates the monophyly of endemic Malagasy primates. Our results support the close relationship of sloth lemurs to living indriids, as has been hypothesized on morphological grounds. In contrast, Megaladapis does not show a sister-group relationship with the living genus Lepilemur. Thus, the classification of the latter in the family Megaladapidae is misleading. By correlating the geographic location of subfossil specimens with relative amplification success, we reconfirm the global trend of increased success rates of ancient DNA recovery from nontropical localities.