Paleogenetics is a relatively new and promising field that has the potential to provide new information about past Indigenous social systems, including insights into the complexity of burial practices. We present results of the first ancient DNA (aDNA) investigation into traditional mortuary practices among Australian Aboriginal people with a focus on North-East Australia. We recovered mitochondrial and Y chromosome sequences from five ancestral Aboriginal Australian remains that were excavated from the Flinders Island group in Cape York, Queensland. Two of these individuals were sampled from disturbed beach burials, while the other three were from bundle burials located in rock shelters. Genomic analyses showed that individuals from all three rock shelter burials and one of the two beach burials had a close genealogical relationship to contemporary individuals from communities from Cape York. In contrast the remaining male individual, found buried on the beach, had a mitochondrial DNA sequence that suggested that he was not from this location but that he was closely related to people from central Queensland or New South Wales. In addition, this individual was associated with a distinctive burial practice to the other four people. It has been suggested that traditionally non-locals or lower status individuals were buried on beaches. Our findings suggest that theories put forward about beach burials being non-local, or less esteemed members of the community, can potentially be resolved through analyses of uniparental genomic data. Generally, these results support the suggestion often derived from ethnohistoric accounts that inequality in Indigenous Australian mortuary practices might be based on the status, sex, and/or age of individuals and may instead relate to place of geographic origin. There is, however, some departure from the traditional ethnohistoric account in that complex mortuary internments were also offered to female individuals of the community, with genomic analyses helping to confirm that the gender of one of the rockshelter internments was that of a young female.