As human populations left Asia to first settle Oceania around 50,000 years ago, they entered a territory ecologically separated from the Old World for millions of years. New Guinea and Australia were then joined into an ancient continent, Sahul, comprising a unique ecosystem that certainly represented an evolutionary challenge for the first settlers. We analyzed genomic data of 239 modern Oceanian individuals to detect and date signals of selection specific to this region. Combining both relative and absolute dating approaches, we identified a strong pattern of genetic adaptations between 52,000 and 54,000 years ago in the genomes of descendants of the first settlers of Sahul. This strikingly corresponds to the dates of initial settlement as inferred from archaeological evidence. Genetic fragments under selection during this period, some showing enrichment in Denisovan ancestry, overlap genes involved in the immune response and diet, especially based on plants. Pathogens and natural resources, especially from endemic plants, therefore appear to have acted as strong selective pressures on the genomes of the first settlers of Sahul.