After European colonization, the ancestral remains of Indigenous people were often collected for scientific research or display in museum collections. For many decades, Indigenous people, including Native Americans and Aboriginal Australians, have fought for their return. However, many of these remains have no recorded provenance, making their repatriation very difficult or impossible. To determine whether DNA-based methods could resolve this important problem, we sequenced 10 nuclear genomes and 27 mitogenomes from ancient pre-European Aboriginal Australians (up to 1540 years before the present) of known provenance and compared them to 100 high-coverage contemporary Aboriginal Australian genomes, also of known provenance. We report substantial ancient population structure showing strong genetic affinities between ancient and contemporary Aboriginal Australian individuals from the same geographic location. Our findings demonstrate the feasibility of successfully identifying the origins of unprovenanced ancestral remains using genomic methods.