The resource-poor, isolated islands of Wallacea have been considered a major adaptive obstacle for hominins expanding into Australasia. Archaeological evidence has hinted that coastal adaptations in Homo sapiens enabled rapid island dispersal and settlement; however, there has been no means to directly test this proposition. Here, we apply stable carbon and oxygen isotope analysis to human and faunal tooth enamel from six Late Pleistocene to Holocene archaeological sites across Wallacea. The results demonstrate that the earliest human forager found in the region c. 42,000 years ago made significant use of coastal resources prior to subsequent niche diversification shown for later individuals. We argue that our data provides clear insights into the huge adaptive flexibility of our species, including its ability to specialize in the use of varied environments, particularly in comparison to other hominin species known from Island Southeast Asia. There has been substantial debate of how hominins colonized Australasia through Wallacea, including their ability to utilize marine vs. terrestrial resources. Here, Roberts et al. use stable carbon and oxygen isotopes to reconstruct temporal shifts in the diets of early human inhabitants of Alor and Timor.