The population history of Aboriginal Australians remains largely uncharacterized. Here we generate high-coverage genomes for 83 Aboriginal Australians (speakers of Pama–Nyungan languages) and 25 Papuans from the New Guinea Highlands. We find that Papuan and Aboriginal Australian ancestors diversified 25–40 thousand years ago (kya), suggesting pre-Holocene population structure in the ancient continent of Sahul (Australia, New Guinea and Tasmania). However, all of the studied Aboriginal Australians descend from a single founding population that differentiated ~10–32 kya. We infer a population expansion in northeast Australia during the Holocene epoch (past 10,000 years) associated with limited gene flow from this region to the rest of Australia, consistent with the spread of the Pama–Nyungan languages. We estimate that Aboriginal Australians and Papuans diverged from Eurasians 51–72 kya, following a single out-of-Africa dispersal, and subsequently admixed with archaic populations. Finally, we report evidence of selection in Aboriginal Australians potentially associated with living in the desert. Whole-genome sequence data for 108 individuals representing 28 language groups across Australia and five language groups for Papua New Guinea suggests that Aboriginal Australians and Papuans diverged from Eurasian populations approximately 60–100 thousand years ago, following a single out-of-Africa dispersal and subsequent admixture with archaic populations. Three international collaborations reporting in this issue of Nature describe 787 high-quality genomes from individuals from geographically diverse populations. David Reich and colleagues analysed whole-genome sequences of 300 individuals from 142 populations. Their findings include an accelerated estimated rate of accumulation of mutations in non-Africans compared to Africans since divergence, and that indigenous Australians, New Guineans and Andamanese do not derive substantial ancestry from an early dispersal of modern humans but from the same source as that of other non-Africans. Eske Willerlsev and colleagues obtained whole-genome data for 83 Aboriginal Australians and 25 Papuans from the New Guinea Highlands. They estimate that Aboriginal Australians and Papuans diverged from Eurasian populations 51,000–72,000 years ago, following a single out-of-Africa dispersal. Luca Pagani et al. report on a dataset of 483 high-coverage human genomes from 148 populations worldwide, including 379 new genomes from 125 populations. Their analyses support the model by which all non-African populations derive most of their genetic ancestry from a single recent migration out of Africa, although a Papuan contribution suggests a trace of an earlier human expansion.