Well-preserved subfossil bones of Adélie penguins, Pygoscelis adeliae, underlie existing and abandoned nesting colonies in Antarctica. These bones, dating back to more than 7000 years before the present, harbor some of the best-preserved ancient DNA yet discovered. From 96 radiocarbon-aged bones, we report large numbers of mitochondrial haplotypes, some of which appear to be extinct, given the 380 living birds sampled. We demonstrate DNA sequence evolution through time and estimate the rate of evolution of the hypervariable region I using a Markov chain Monte Carlo integration and a least-squares regression analysis. Our calculated rates of evolution are approximately two to seven times higher than previous indirect phylogenetic estimates.