The existence of a short-statured Aboriginal population in the Far North Queensland (FNQ) rainforest zone of Australia’s northeast coast and Tasmania has long been an enigma in Australian anthropology. Based on their reduced stature and associated morphological traits such as tightly curled hair, Birdsell and Tindale proposed that these “Barrinean” peoples were closely related to “negrito” peoples of Southeast Asia and that their ancestors had been the original Pleistocene settlers of Sahul, eventually displaced by taller invaders. Subsequent craniometric and blood protein studies, however, have suggested an overall homogeneity of indigenous Australians, including Barrineans. To confirm this finding and determine the degree of relatedness between Barrinean people and Southeast Asian negritos, we compared indigenous Australian mitochondrial DNA (mtDNA) sequences in populations from the FNQ rainforest ecozone and Tasmania with sequences from other Australian Aboriginal populations and from Southeast Asian negrito populations (Philippines Batek and Mamanwa, and mainland Southeast Asian Jahai, Mendriq, and Batak). The results confirm that FNQ and Tasmanian mtDNA haplogroups cluster with those of other Australian Aboriginal populations and are only very distantly related to Southeast Asian negrito haplogroups.