It is well accepted that the Americas were the last continents reached by modern humans, most likely through Beringia. However, the precise time and mode of the colonization of the New World remain hotly disputed issues. Native American populations exhibit almost exclusively five mitochondrial DNA (mtDNA) haplogroups (A-D and X). Haplogroups A-D are also frequent in Asia, suggesting a northeastern Asian origin of these lineages. However, the differential pattern of distribution and frequency of haplogroup X led some to suggest that it may represent an independent migration to the Americas. Here we show, by using 86 complete mitochondrial genomes, that all Native American haplogroups, including haplogroup X, were part of a single founding population, thereby refuting multiple-migration models. A detailed demographic history of the mtDNA sequences estimated with a Bayesian coalescent method indicates a complex model for the peopling of the Americas, in which the initial differentiation from Asian populations ended with a moderate bottleneck in Beringia during the last glacial maximum (LGM), around approximately 23,000 to approximately 19,000 years ago. Toward the end of the LGM, a strong population expansion started approximately 18,000 and finished approximately 15,000 years ago. These results support a pre-Clovis occupation of the New World, suggesting a rapid settlement of the continent along a Pacific coastal route.