The exact timing, route, and process of the initial peopling of the Americas remains uncertain despite much research. Archaeological evidence indicates the presence of humans as far as southern Chile by 14.6 thousand years ago (ka), shortly after the Pleistocene ice sheets blocking access from eastern Beringia began to retreat. Genetic estimates of the timing and route of entry have been constrained by the lack of suitable calibration points and low genetic diversity of Native Americans. We sequenced 92 whole mitochondrial genomes from pre-Columbian South American skeletons dating from 8.6 to 0.5 ka, allowing a detailed, temporally calibrated reconstruction of the peopling of the Americas in a Bayesian coalescent analysis. The data suggest that a small population entered the Americas via a coastal route around 16.0 ka, following previous isolation in eastern Beringia for similar to 2.4 to 9 thousand years after separation from eastern Siberian populations. Following a rapid movement throughout the Americas, limited gene flow in South America resulted in a marked phylogeographic structure of populations, which persisted through time. All of the ancient mitochondrial lineages detected in this study were absent from modern data sets, suggesting a high extinction rate. To investigate this further, we applied a novel principal components multiple logistic regression test to Bayesian serial coalescent simulations. The analysis supported a scenario in which European colonization caused a substantial loss of pre-Columbian lineages.