To study the evolutionary history of the Australian and New Guinean indigenous peoples, we analyzed 101 complete mitochondrial genomes including populations from Australia and New Guinea as well as from Africa, India, Europe, Asia, Melanesia, and Polynesia. The genetic diversity of the Australian mitochondrial sequences is remarkably high and is similar to that found across Asia. This is in contrast to the pattern seen in previously described Y-chromosome data where an Australia-specific haplotype was found at high frequency. The mitochondrial genome data indicate that Australia was colonized between 40 and 70 thousand years ago, either by a single migration from a heterogeneous source population or by multiple movements of smaller groups occurring over a period of time. Some Australian and New Guinea sequences form clades, suggesting the possibility of a joint colonization and/or admixture between the two regions.