Controversy exists over the cause and timing of the extinction of the Pleistocene megafauna. In the tropical Andes, deglaciation and associated rapid climate change began ∼8,000 years before human arrival, providing an opportunity to separate the effects of climate change from human hunting on megafaunal extinction. We present a paleoecological record spanning the last 25,000 years from Lake Pacucha, Peru (3,100 m elevation). Fossil pollen, charcoal, diatoms, and the dung fungus Sporormiella, chronicle a two-stage megaherbivore population collapse. Sporormiella abundance, the proxy for megafaunal presence, fell sharply at ∼21,000 years ago, but rebounded prior to a permanent decline between ∼16,800 and 15,800 years ago. This two-stage decline in megaherbivores resulted in a functional extinction by ∼15,800 years ago, 3,000 years earlier than known human occupation of the high Andes. Declining megaherbivore populations coincided with warm, wet intervals. Climatic instability and megafaunal population collapse triggered an ecological cascade that resulted in novel floral assemblages, and increases in woody species, fre frequency, and plant species that were sensitive to trampling. Our data revealed that Andean megafaunal populations collapsed due to positive feedbacks between habitat quality and climate change rather than human activity.