Archaeological deposits from Boodie Cave on Barrow Island, northwest Australia, reveal some of the oldest evidence for Aboriginal occupation of Australia, as well as illustrating the early use of marine resources by modern peoples outside of Africa. Barrow Island is a large (202 km2) limestone continental island located on the North-West Shelf of Australia, optimally located to sample past use of both the Pleistocene coastline and extensive arid coastal plains. An interdisciplinary team forming the Barrow Island Archaeology Project (BIAP) has addressed questions focusing on the antiquity of occupation of coastal deserts by hunter-gatherers; the use and distribution of marine resources from the coast to the interior; and the productivity of the marine zone with changing sea levels. Boodie Cave is the largest of 20 stratified deposits identified on Barrow Island with 20 m3 of cultural deposits excavated between 2013 and 2015. In this first major synthesis we focus on the dating and sedimentology of Boodie Cave to establish the framework for ongoing analysis of cultural materials. We present new data on these cultural assemblages – including charcoal, faunal remains and lithics – integrated with micromorphology, sedimentary history and dating by four independent laboratories. First occupation occurs between 51.1 and 46.2 ka, overlapping with the earliest dates for occupation of Australia. Marine resources are incorporated into dietary assemblages by 42.5 ka and continue to be transported to the cave through all periods of occupation, despite fluctuating sea levels and dramatic extensions of the coastal plain. The changing quantities of marine fauna through time reflect the varying distance of the cave from the contemporaneous shoreline. The dietary breadth of both arid zone terrestrial fauna and marine species increases after the Last Glacial Maximum and significantly so by the mid-Holocene. The cave is abandoned by 6.8 ka when the island becomes increasingly distant from the mainland coast.