Studying the genetic history of the Orang Asli of Peninsular Malaysia can provide crucial clues to the peopling of Southeast Asia as a whole. We have analyzed mitochondrial DNA (mtDNAs) control-region and coding-region markers in 447 mtDNAs from the region, including 260 Orang Asli, representative of each of the traditional groupings, the Semang, the Senoi, and the Aboriginal Malays, allowing us to test hypotheses about their origins. All of the Orang Asli groups have undergone high levels of genetic drift, but phylogeographic traces nevertheless remain of the ancestry of their maternal lineages. The Semang have a deep ancestry within the Malay Peninsula, dating to the initial settlement from Africa >50,000 years ago. The Senoi appear to be a composite group, with approximately half of the maternal lineages tracing back to the ancestors of the Semang and about half to Indochina. This is in agreement with the suggestion that they represent the descendants of early Austroasiatic speaking agriculturalists, who brought both their language and their technology to the southern part of the peninsula approximately 4,000 years ago and coalesced with the indigenous population. The Aboriginal Malays are more diverse, and although they show some connections with island Southeast Asia, as expected, they also harbor haplogroups that are either novel or rare elsewhere. Contrary to expectations, complete mtDNA genome sequences from one of these, R9b, suggest an ancestry in Indochina around the time of the Last Glacial Maximum, followed by an early-Holocene dispersal through the Malay Peninsula into island Southeast Asia.