In Australia, cultural-ecological narratives that commence with Western connections to marine systems or species, eclipse Indigenous cultural connections that date back in memmorial. The devastating impacts of commercial sealing in the early 1800’s, followed by long-nosed fur seal (Arctocephalus forsteri) population increases in South Australia, primarily over the last two decades, largely define Western scientific understandings of the species reboudning population trajectories. To recover a lost baseline of seal abundances and provide a more holistic cultural-ecological perspective of recovery, we report on the metapopulation trends of long-nosed fur seals across south-eastern Australia and contextualise key shifts in the human-seal relationship across three key time periods; (1) archaeological and anthropological insights regarding Aboriginal sealing, (2) colonial sealing and (3) the legislative protection of seals and their recovery. This study shows that seal and human interactions have been inextricably linked for at least 11,000 years in south-east Australia. Our results demonstrate significant shifts in seal species diversity and range due to a high reliance on seal meat that shaped semi-sedentary coastal lifestyles amongst several Aboriginal groups prior to Western colonisation. Such insights help re-define what seal recovery may look like into the future and provide research and management platforms that connect with Australia’s rich Aboriginal past, present and future.