There are many unanswered questions about the population history of the Central and South Central Andes, particularly regarding the impact of large-scale societies, such as the Moche, Wari, Tiwanaku, and Inca. We assembled genome-wide data on 89 individuals dating from ∼9,000-500 years ago (BP), with a particular focus on the period of the rise and fall of state societies. Today's genetic structure began to develop by 5,800 BP, followed by bi-directional gene flow between the North and South Highlands, and between the Highlands and Coast. We detect minimal admixture among neighboring groups between ∼2,000-500 BP, although we do detect cosmopolitanism (people of diverse ancestries living side-by-side) in the heartlands of the Tiwanaku and Inca polities. We also highlight cases of long-range mobility connecting the Andes to Argentina and the Northwest Andes to the Amazon Basin. VIDEO ABSTRACT.