After their emergence by 200,000 years before the present in Africa, modern humans colonized the globe, reaching Australia and New Guinea by 40,000 to 50,000 years ago. Understanding how humans lived and adapted to the range of environments in these areas has been difficult because well-preserved settlements are scarce. Data from the New Guinea Highlands (at an elevation of ~2000 meters) demonstrate the exploitation of the endemic nut Pandanus and yams in archaeological sites dated to 49,000 to 36,000 years ago, which are among the oldest human sites in this region. The sites also contain stone tools thought to be used to remove trees, which suggests that the early inhabitants cleared forest patches to promote the growth of useful plants.