The genetic history of Southern East Asians is not well-known, especially prior to the Neolithic period. To address this, we successfully sequenced two complete mitochondrial genomes of 11,000-year-old human individuals from Southern China, thus generating the oldest ancient DNA sequences from this area. Integrating published mitochondrial genomes, we characterized M71d, a new subhaplogroup of haplogroup M71. Our results suggest a possible early migration between Southern China and mainland Southeast Asia by at least 22,000 BP.