DNA from ancient human remains provides perspectives on the origin of our species and the relationship between molecular and morphological variation. We report analysis of mtDNA from the remains of 10 ancient Australians. These include the morphologically gracile Lake Mungo 3 [ approximately 60 thousand years (ka) before present] and three other gracile individuals from Holocene deposits at Willandra Lakes (<10 ka), all within the skeletal range of living Australians, and six Pleistocene/early Holocene individuals (15 to <8 ka) from Kow Swamp with robust morphologies outside the skeletal range of contemporary indigenous Australians. Lake Mungo 3 is the oldest (Pleistocene) "anatomically modern" human from whom DNA has been recovered. His mtDNA belonged to a lineage that only survives as a segment inserted into chromosome 11 of the nuclear genome, which is now widespread among human populations. This lineage probably diverged before the most recent common ancestor of contemporary human mitochondrial genomes. This timing of divergence implies that the deepest known mtDNA lineage from an anatomically modern human occurred in Australia; analysis restricted to living humans places the deepest branches in East Africa. The other ancient Australian individuals we examined have mtDNA sequences descended from the most recent common ancestor of living humans. Our results indicate that anatomically modern humans were present in Australia before the complete fixation of the mtDNA lineage now found in all living people. Sequences from additional ancient humans may further challenge current concepts of modern human origins.