While Australia is unique in having one of the longest continuous period of human occupation outside Africa, its population history remains largely uncharacterized. The distinctiveness of the Australian archaeological record has led to the suggestion that the ancestors of Aboriginal Australians and Papuans are modern representatives of an early dispersal of modern humans out of Africa. To describe the origins of Aboriginal Australians, as well as their differentiation, adaptation and relatedness to other populations, we collected DNA sampled in collaboration with Aboriginal Australian communities and individuals in Australia. We sequenced genomes at high-depth from Aboriginal Australian individuals. The sequenced individuals represent a number Pama Nyungan languages and originate from regions geographically widespread across the Australian continent. Combining this dataset with whole genome data from Africans and Eurasians we investigated the number of migration waves out of Africa, explicitly taking archaic introgression into account. Based on the site-frequency spectrum we estimate that Aboriginal Australians and Eurasians derive mostly from a single out of Africa wave. Furthermore, we find that Papuan and Aboriginal Australian ancestors diverged long before Australia and New Guinea were separated by higher sea levels, suggesting early population structure in the ancient continent of Sahul (Australia, New Guinea and Tasmania). As expected, we detect European and East Asian admixture across most of the modern Aboriginal Australian groups included in the study. Finally, once we account for this recent admixture we find that genetics mirrors both geography and linguistics.