Human presence in Sahul, the ancient continent encompassing Australia, Tasmania and New Guinea, dates back to ~50 kya. Papua New Guinea has a varied, mountainous geography and has attracted long-standing anthropological interest because of its great human cultural and linguistic diversity. Genetic studies so far have however been small and mostly limited to a few markers and/or the uniparental chromosomes. We have genotyped 382 individuals from Papua New Guinea on the 1.7 million sites of the Infinium Multi-Ethnic Global array. Our sample includes individuals from 18 of the 22 provinces and covers dozens of geographically and linguistically distinct groups within the highlands and the northern and southern lowlands. We find that most groups have remained unaffected by external gene flow into the region since the initial settlement of Sahul. We find strong population structure and high genetic differentiation – many FST values between groups within the highlands are larger than those between major populations within the continents of Europe or East Asia. Using relative cross coalescence rates between high-coverage genome sequences from selected populations we estimate that this differentiation has formed mostly within the last 10 ky. This study provides the first comprehensive overview of human population history and structure in this historically and anthropologically important part of the world.