Hmong-Mien (H-M) is a major language family in East Asia, and its speakers distribute primarily in southern China and Southeast Asia. To date, genetic studies on H-M speaking populations are virtually absent in the literature. In this report, we present the results of an analysis of genetic variations in the mitochondrial DNA (mtDNA) hypervariable segment 1 (HVS1) region and diagnostic variants in the coding regions in 537 individuals sampled from 17 H-M populations across East Asia. The analysis showed that the haplogroups that are predominant in southern East Asia, including B, R9, N9a, and M7, account for 63% (ranging from 45% to 90%) of mtDNAs in H-M populations. Furthermore, analysis of molecular variance (AMOVA), phylogenetic tree analysis, and principal component (PC) analysis demonstrate closer relatedness between H-M and other southern East Asians, suggesting a general southern origin of maternal lineages in the H-M populations. The estimated ages of the mtDNA lineages that are specific to H-M coincide with those based on archeological cultures that have been associated with H-M. Analysis of genetic distance and phylogenetic tree indicated some extent of difference between the Hmong and the Mien populations. Together with the higher frequency of north-dominating lineages observed in the Hmong people, our results indicate that the Hmong populations had experienced more contact with the northern East Asians, a finding consistent with historical evidence. Moreover, our data defined some new (sub-)haplogroups (A6, B4e, B4f, C5, F1a1, F1a1a, and R9c), which will direct further efforts to improve the phylogeny of East Asian mtDNAs.