The Wallacea Archipelago provides an extraordinary laboratory for the study of human colonisation and adaptation, yet few detailed archaeological studies have been conducted in the region that span the earliest phase of human settlement. Laili Cave, in northern Timor-Leste, preserves the oldest human occupation in this insular region with a cultural sequence spanning 11,200 to 44,600 cal BP. Small-bodied vertebrates and invertebrates were recovered to the lowest excavated levels, associated with highly concentrated stone artefacts. We report on human behavioural adaptations within the context of Pleistocene environments and changing landscapes using zooarchaeological, stone artefact, bathymetric, and experimental isotopic analyses. Results indicate that Pleistocene humans used the abundant local chert liberally and engaged in mobile broad-spectrum exploitation of invertebrates and fishes from marine, estuarine, and freshwater environments within close proximity of Laili Cave. The faunal assemblage indicates heterogeneous but relatively stable environments during the late Pleistocene. Variability in subsistence strategies over time appears to be a response to changing landscapes and concomitant local resources. This record contrasts with marine specialisations evident from other sites in Timor-Leste and within the broader Wallacean region.