Y-chromosome specific STR profiling is increasingly used in forensic casework. However, the strong geographic clustering of Y haplogroups can lead to large differences in Y-STR haplotype frequencies between different ethnicities, which may have an impact on database composition in admixed populations. Aboriginal people have inhabited Australia for over 40,000 years and until ∼300 years ago they lived in almost complete isolation. Since the late 18th century Australia has experienced massive immigration, mainly from Europe, although in recent times from more widespread origins. This colonisation resulted in highly asymmetrical admixture between the immigrants and the indigenes. A State jurisdiction within Australia has created an Aboriginal Y-STR database in which assignment of ethnicity was by self-declaration. This criterion means that some males who identify culturally as members of a particular ethnic group may have a Y haplogroup characteristic of another ethnic group, as a result of admixture in their paternal line. As this may be frequent in Australia, an examination of the extent of genetic admixture within the database was performed. A Y haplogroup predictor program was first used to identify Y haplotypes that could be assigned to a European haplogroup. Of the 757 males (589 unique haplotypes), 445 (58.8%) were identified as European (354 haplotypes). The 312 non-assigned males (235 haplotypes) were then typed, in a hierarchical fashion, with a Y-SNP panel that detected the major Y haplogroups, C-S, as well as the Aboriginal subgroup of C, C4. Among these 96 males were found to have non-Aboriginal haplogroups. In total, ∼70% of Y chromosomes in the Aboriginal database could be classed as non-indigenous, with only 169 (129 unique haplotypes) or 22% of the total being associated with haplogroups denoting Aboriginal ancestry, C4 and K* or more correctly K(xL,M,N,O,P,Q,R,S). The relative frequencies of these indigenous haplogroups in South Australia (S.A.) were significantly different to those seen in samples from the Northern Territory and Western Australia. In S.A., K* (∼60%) has a much higher frequency than C4 (∼40%), and the subgroup of C4, C4(DYS390.1del), comprised only 17%. Clearly admixture in the paternal line is at high levels among males who identify themselves as Australian Aboriginals and this knowledge may have implications for the compilation and use of Y-STR databases in frequency estimates.