If we want to find the earliest evidence of human occupation in Australia, we need to look in our oceans. This is because when those early seafarers first stepped foot on the Australian continent some 65,000 years ago, sea levels were almost 100 m lower than they are today. Following the termination of the last ice age around 18,000 years ago, the ice sheets retreated, and sea levels rose by 130 m. The generations of people living though this time would have only known retreat, inland and to higher ground. The rising seas inundated their homelands, cutting off spiritually significant sites and places whose cultural connections had spanned countless 1000’s of generations of people. By the time sea levels stabilised around 7,000 years ago over 2 million square km of land was inundated. What now exists under the sea is a lost archive of one of humanity’s earliest and most enduring cultures. Here we report on recent discoveries of submerged stone tool scatters on the seafloor around Murujuga (Dampier Archipelago), as well as the development of novel scientific and ethnographic approaches, in collaboration with Murujuga’s Traditional Owners, to better locate and identify submerged rock art sites.