Mating systems are thought to be an important determinant of dispersal strategies in most animals, including the great apes. As the most basal taxon of all great apes, orang-utans can provide information about the evolution of mating systems and their consequences for population structure in this Family. To assess the sex-specific population structure in orang-utans, we used a combination of paternally transmitted Y-chromosomal genetic markers and maternally transmitted mitochondrial DNA sequences. Markers transmitted through the more philopatric sex are expected to show stronger differentiation among populations than the ones transmitted through the dispersing sex. We studied these patterns using 70 genetic samples from wild orang-utans from seven Bornean and two Sumatran populations. We found pronounced population structure in haplotype networks of mitochondrial sequence data, but much less so for male-specific markers. Similarly, mitochondrial genetic differentiation was twice as high among populations compared to Y-chromosomal variation. We also found that genetic distance increased faster with geographic distance for mitochondrial than for Y-linked markers, leading to estimates of male dispersal distances that are several-fold higher than those of females. These findings provide evidence for strong male-biased dispersal in orang-utans. The transition to predominantly female-biased dispersal in the great ape lineage appears to be correlated with life in multimale groups and may reflect the associated fitness benefits of reliable male coalitions with relatives or known partners, a feature that is absent in orang-utans.