BACKGROUND: Long-tailed macaques (Macaca fascicularis) are an important model species in biomedical research and reliable knowledge about their evolutionary history is essential for biomedical inferences. Ten subspecies have been recognized, of which most are restricted to small islands of Southeast Asia. In contrast, the common long-tailed macaque (M. f. fascicularis) is distributed over large parts of the Southeast Asian mainland and the Sundaland region. To shed more light on the phylogeny of M. f. fascicularis, we sequenced complete mitochondrial (mtDNA) genomes of 40 individuals from all over the taxon's range, either by classical PCR-amplification and Sanger sequencing or by DNA-capture and high-throughput sequencing. RESULTS: Both laboratory approaches yielded complete mtDNA genomes from M. f. fascicularis with high accuracy and/or coverage. According to our phylogenetic reconstructions, M. f. fascicularis initially diverged into two clades 1.70 million years ago (Ma), with one including haplotypes from mainland Southeast Asia, the Malay Peninsula and North Sumatra (Clade A) and the other, haplotypes from the islands of Bangka, Java, Borneo, Timor, and the Philippines (Clade B). The three geographical populations of Clade A appear as paraphyletic groups, while local populations of Clade B form monophyletic clades with the exception of a Philippine individual which is nested within the Borneo clade. Further, in Clade B the branching pattern among main clades/lineages remains largely unresolved, most likely due to their relatively rapid diversification 0.93-0.84 Ma. CONCLUSIONS: Both laboratory methods have proven to be powerful to generate complete mtDNA genome data with similarly high accuracy, with the DNA-capture and high-throughput sequencing approach as the most promising and only practical option to obtain such data from highly degraded DNA, in time and with relatively low costs. The application of complete mtDNA genomes yields new insights into the evolutionary history of M. f. fascicularis by providing a more robust phylogeny and more reliable divergence age estimations than earlier studies.