The peopling of the Andean highlands above 2500 m in elevation was a complex process that included cultural, biological, and genetic adaptations. Here, we present a time series of ancient whole genomes from the Andes of Peru, dating back to 7000 calendar years before the present (BP), and compare them to 42 new genome-wide genetic variation datasets from both highland and lowland populations. We infer three significant features: a split between low- and high-elevation populations that occurred between 9200 and 8200 BP; a population collapse after European contact that is significantly more severe in South American lowlanders than in highland populations; and evidence for positive selection at genetic loci related to starch digestion and plausibly pathogen resistance after European contact. We do not find selective sweep signals related to known components of the human hypoxia response, which may suggest more complex modes of genetic adaptation to high altitude.