Population structure has been revealed in mitochondrial D-loop segment 1 (mt DLS1) sequences from Australian Aboriginal people in the Darling River region of NSW (Riverine) and from Yuendumu in central Australia (Desert). Comparison with five published global studies reveals that these Australians demonstrate greatest divergence from some Africans, least from Papua New Guinea (PNG) highlanders, and only slightly more divergence from some Pacific groups (Indonesian, Asian, Samoan, and coastal PNG). A median networks approach demonstrates that several hypervariable nucleotide sites within the DLS1 are likely to have undergone mutation independently. A comprehensive evaluation of specific nucleotide variants with the large amount of global sequence data now available has been achieved in three stages of analysis: (i) identification of key nucleotide variants (from the Cambridge reference sequence) in the Aboriginal Australian by pairwise comparison and construction of a 'local' median network, (ii) identification of key nucleotide variants in a selected global sample including Australian mtDLS1 types most different from each other, and (iii) calculation of the frequency with which these key nucleotide sites occur as variants in a greatly extended global sample. The third stage of the analysis revealed that nucleotides 16287 and 16356 are unique markers for representatives from the northern Riverine region. A 'thymine' at nucleotide 16223 is an informative signature of African and several identifiable non-African DLS1 types, whereas the 'cytosine' form is a marker for European, Pacific, and some Asian populations.