We report archaeological findings from a significant new cave site on Alor Island, Indonesia, with an in situ basal date of 40,208-38,454 cal BP. Twenty thousand years older than the earliest Pleistocene site previously known from this island, Makpan retains dense midden deposits of marine shell, fish bone, urchin and crab remains, but few terrestrial species; demonstrating that protein requirements over this time were met almost exclusively from the sea. The dates for initial occupation at Makpan indicate that once Homo sapiens moved into southern Wallacea, settlement of the larger islands in the archipelago occurred rapidly. However, the Makpan sequence also suggests that the use of the cave following initial human arrival was sporadic prior to the terminal Pleistocene about 14,000 years ago, when occupation became intensive, culminating in the formation of a midden. Like the coastal sites on the larger neighbouring island of Timor, the Makpan assemblage shows that maritime technology in the Pleistocene was highly developed in this region. The Makpan assemblage also contains a range of distinctive personal ornaments made on Nautilus shell, which are shared with sites located on Timor and Kisar supporting connectivity between islands from at least the terminal Pleistocene. Makpan's early inhabitants responded to sea-level change by altering the way they used both the site and local resources. Marine food exploitation shows an initial emphasis on sea-urchins, followed by a subsistence switch to molluscs, barnacles, and fish in the dense middle part of the sequence, with crabs well represented in the later occupation. This new record provides further insights into early modern human movements and patterns of occupation between the islands of eastern Nusa Tenggara from ca. 40 ka.