We outline the Aboriginal Heritage Project: a collaboration between the Australian Centre of Ancient DNA (ACAD) and the South Australian Museum (SAM) that aims to reconstruct the genetic history of Aboriginal Australia. The project leverages the unparalleled collection of 5000+ hair samples curated by the SAM along with cultural, morphometric and genealogical data, which were collated by Joseph B. Birdsell and Norman B. Tindale during extensive anthropological expeditions across Australia between 1926 and 1963. The broad geographic sampling and unique combination of ancient DNA and deep genealogies contained in the SAM collection provides perhaps our best opportunity to understand Aboriginal Australian genetic history prior to European colonisation. We present our outreach activities, which crucially involve re-consenting the hair samples through in-depth consultation with Aboriginal families and communities, along with preliminary phylogeographic analyses which reveal that pre-colonial Aboriginal Australia was characterised by deeply structured populations dating back to the initial colonisation of the continent. Ultimately, we aim to create a reference map that allows current and future generations of Aboriginal Australians to retrace their ancestry - including the displaced Stolen Generations and their descendants - and illuminates this remarkable but still largely unknown chapter of human genetic history to the rest of world.