New Guinea's mountains provide an important case study for understanding early modern human environmental adaptability and early developments leading to agriculture. Evidence is presented showing that human colonization pre-dated 35ka (ka = thousands of uncalibrated radiocarbon years before present) and was accompanied by landscape modification using fire. Sorties into the subalpine zone may have occurred before the Late Glacial Maximum (LGM), and perhaps contributed to megafaunal extinction. Humans persisted in the intermontane valleys through the LGM and expanded rapidly into the subalpine on climatic warming, when burning and clearance may have retarded vegetation re-colonization. Plant food use dates from at least 31ka, confirming that some of New Guinea's distinctive agricultural practices date to the earliest millennia of human presence.