The Tyrolean Iceman was a witness to the Neolithic-Copper Age transition in Central Europe 5350-5100 years ago, and his mummified corpse was recovered from an Alpine glacier on the Austro-Italian border in 1991 [1]. Using a mixed sequencing procedure based on PCR amplification and 454 sequencing of pooled amplification products, we have retrieved the first complete mitochondrial-genome sequence of a prehistoric European. We have then compared it with 115 related extant lineages from mitochondrial haplogroup K. We found that the Iceman belonged to a branch of mitochondrial haplogroup K1 that has not yet been identified in modern European populations. This is the oldest complete Homo sapiens mtDNA genome generated to date. The results point to the potential significance of complete-ancient-mtDNA studies in addressing questions concerning the genetic history of human populations that the phylogeography of modern lineages is unable to tackle.