A comparison of mitochondrial DNA sequences was undertaken for two genes among orangutans from Borneo and Sumatra. The distribution of haplotypes among 42 individuals for NADH dehydrogenease subunit 3 and 39 individuals for cytochrome B was used to infer population structure. The haplotypes among all Bornean orangutans form a cluster of closely related individuals for both genes, with two distinct haplotypes occupying different regions of the island. Sumatran haplotypes fall into three distinct, and highly diverged, groups. Strikingly, one of the Sumatran haplotypes shares sequence identity with the most widespread Bornean haplotype. This haplotype distribution is considered in the context of the highly complex geological history for the area around the Malay Archipelago. Alternating periods of geographic isolation and reunion, resulting from glacially induced land bridge formation, presented substantial opportunity for population dispersal between periodically isolated demes. We present a paleodispersal model that is consistent with genetic, geological, paleoecological, and fossil data. The disparity of sequences present in orangutan populations argues against a simple Sumatra–Borneo dichotomy. Our evidence, and that of others, suggests that the Sumatran population alone contains the remnants of at least three separate lineages.