Many efforts based on complete mitochondrial DNA (mtDNA) genomes have been made to depict the global mtDNA landscape, but the phylogeny of Indian macrohaplogroup M has not yet been resolved in detail. To fill this lacuna, we took the same strategy as in our recent analysis of Indian mtDNA macrohaplogroup N and selected 56 mtDNAs from over 1,200 samples across India for complete sequencing, with the intention to cover all Indian autochthonous M lineages. As a result, the phylogenetic status of previously identified haplogroups based on control-region and/or partial coding-region information, such as M2, M3, M4, M5, M6, M30, and M33, was solidified or redefined here. Moreover, seven novel basal M haplogroups (viz., M34-M40) were identified, and yet another five singular branches of the M phylogeny were discovered in the present study. The comparison of matrilineal components among India, East Asia, Southeast Asia, and Oceania at the deepest level yielded a star-like and nonoverlapping pattern, reflecting a rapid mode of modern human dispersal along the Asian coast after the initial "out-of-Africa" event.