Abstract Background An early dispersal of biologically and behaviorally modern humans from their African origins to Australia, by at least 45 thousand years via southern Asia has been suggested by studies based on morphology, archaeology and genetics. However, mtDNA lineages sampled so far from south Asia, eastern Asia and Australasia show non-overlapping distributions of haplogroups within pan Eurasian M and N macrohaplogroups. Likewise, support from the archaeology is still ambiguous. Results In our completely sequenced 966-mitochondrial genomes from 26 relic tribes of India, we have identified seven genomes, which share two synonymous polymorphisms with the M42 haplogroup, which is specific to Australian Aborigines. Conclusion Our results showing a shared mtDNA lineage between Indians and Australian Aborigines provides direct genetic evidence of an early colonization of Australia through south Asia, following the "southern route".