As genomic medicine becomes more sophisticated, it is important to ensure that key advances are not enjoyed primarily by people from a handful of well-represented human ancestries. The Indigenous communities of Australia are currently poorly characterised in a genomic context, and under-represented in reference panels. To address this, the National Centre for Indigenous Genomics (NCIG) has collected genomic data from four Indigenous Australian communities from across a wide expanse of the continent. We present a study of the patterns of genetic variation and diversity within this dataset and emphasise how this underpins future health and disease research for Indigenous Australians. After applying local ancestry inference models to systematically mask regions of the genome inherited from non-Indigenous ancestors, this analysis describes the extreme degree of population structure seen within the Indigenous Australian dataset. The results are contextualised through comparisons to human populations separated by similar distances within other continents of the world, and the medical and genomic implications of the immense degree of structure, haplotype and rare allele sharing within the Indigenous Australian communities discussed. We also uncover much previously uncharacterised genetic variation in Indigenous Australians when compared to worldwide populations, calling into question the utility of global reference panels and databases for conducting research within these communities. Finally, analysis of the Indigenous Australian data alongside groups from the surrounding Oceanic region reveals a long and likely complex history of genetic interaction between the populations of northern Australia and Melanesia, with consequences for genomic medicine and research.