Oceania is a key region for studying human dispersals, adaptations and interactions with other hominin populations. Although archaeological evidence now reveals occupation of the region by approximately 65-45 000 years ago, its human fossil record, which has the best potential to provide direct insights into ecological adaptations and population relationships, has remained much more elusive. Here, we apply radiocarbon dating and stable isotope approaches to the earliest human remains so far excavated on the islands of Near and Remote Oceania to explore the chronology and diets of the first preserved human individuals to step across these Pacific frontiers. We demonstrate that the oldest human (or indeed hominin) fossil outside of the mainland New Guinea-Aru area dates to approximately 11 800 years ago. Furthermore, although these early sea-faring populations have been associated with a specialized coastal adaptation, we show that Late Pleistocene-Holocene humans living on islands in the Bismarck Archipelago and in Vanuatu display a persistent reliance on interior tropical forest resources. We argue that local tropical habitats, rather than purely coasts or, later, arriving domesticates, should be emphasized in discussions of human diets and cultural practices from the onset of our species' arrival in this part of the world. This article is part of the theme issue 'Tropical forests in the deep human past'.