The Tanimbar Islands are uniquely located at the most easterly extent of the southern Wallacean island chain. Despite their close proximity to the Sahul continental shelf, and unlike similar Sahul-proximity islands to the north and south, the Tanimbar Islands have only received minimal archaeological attention to date. Extensive surveys conducted by Balai Arkeologi Ambon had indicated the high archaeological potential in the islands, from Neolithic to Palaeolithic. Here we present the initial results of our recent survey efforts and the excavation of Elivavan rockshelter on the Tanimbar’s north-east-most island Fordata. The Elivavan excavation recovered evidence for intensive coastal invertebrate exploitation (i.e. mollusc and crab) as well as a number of intriguing macropod remains. The majority of the mollusc taxa are from sandy shore-type habitats similar to those present on nearby beaches today. The possibility of prehistoric wallaby exploitation on an island of biogeographic significance where there is no modern or historical record of macropods on these islands is really noteworthy. Similar to the Dorcopsis remains recovered from Golo Cave on Gebe Island to the north, the presence of this mysterious macropod raises questions of how it arrived on the island, either by natural or anthropogenic means, and what caused it to later disappear? We reflect on this new archaeological record in light of how the early Tanimbar peoples adapted to changes in environmental conditions and resource availability.