The origins and genetic affinities of the more than 500 tribal populations living in South Asia are widely disputed. This may reflect differential contributions that continental populations have made to tribal groups in South Asia. We assayed for the presence of the intergenic COII/tRNALys 9-bp deletion in human mtDNA in 646 individuals from 12 caste and 14 tribal populations of South India and compared them to individuals from Africa, Europe, and Asia. The 9-bp deletion is observed in four South Indian tribal populations, the Irula, Yanadi, Siddi, and Maria Gond, and in the Nicobarese. Length polymorphisms of the 9-bp motif are present in the Santal, Khonda Dora, and Jalari, all of whom live in a circumscribed region on the eastern Indian coast. Phylogenetic analyses of mtDNA control region sequence from individuals with the 9-bp deletion indicate that it has arisen independently in some Indian tribal populations. Other 9-bp deletion haplotypes are likely to be of Asian and African origin, implying multiple origins of the 9-bp deletion in South India. These results demonstrate varying genetic affinities of different South Indian tribes to continental populations and underscore the complex histories of the tribal populations living in South Asia.