Objective Understanding the origins of Aboriginal Australians is crucial in reconstructing the evolution and spread of Homo sapiens as evidence suggests they represent the descendants of the earliest group to leave Africa. This study analyzed a large sample of Y-chromosomes to answer questions relating to the migration routes of their ancestors, the age of Y-haplogroups, date of colonization, as well as the extent of male-specific variation. Methods Knowledge of Y-chromosome variation among Aboriginal Australians is extremely limited. This study examined Y-SNP and Y-STR variation among 657 self-declared Aboriginal males from locations across the continent. 17 Y-STR loci and 47 Y-SNPs spanning the Y-chromosome phylogeny were typed in total. Results The proportion of non-indigenous Y-chromosomes of assumed Eurasian origin was high, at 56%. Y lineages of indigenous Sahul origin belonged to haplogroups C-M130(xM8,M38,M217,M347) (1%), C-M347 (19%), K-M526(xM147,P308,P79,P261,P256,M231,M175,M45,P202) (12%), S-P308 (12%), and M-M186 (0.9%). Haplogroups C-M347, K-M526, and S-P308 are Aboriginal Australian-specific. Dating of C-M347, K-M526, and S-P308 indicates that all are at least 40,000 years old, confirming their long-term presence in Australia. Haplogroup C-M347 comprised at least three sub-haplogroups: C-DYS390.1del, C-M210, and the unresolved paragroup C-M347(xDYS390.1del,M210). Conclusions There was some geographic structure to the Y-haplogroup variation, but most haplogroups were present throughout Australia. The age of the Australian-specific Y-haplogroups suggests New Guineans and Aboriginal Australians have been isolated for over 30,000 years, supporting findings based on mitochondrial DNA data. Our data support the hypothesis of more than one route (via New Guinea) for males entering Sahul some 50,000 years ago and give no support for colonization events during the Holocene, from either India or elsewhere. Am J Phys Anthropol 159:367-381, 2016.