Mesoamerica has an important role in the expansion of Paleoamericans as the route to South America. In this study, we determined complete mitogenome sequences of 113 unrelated individuals from two indigenous populations of Mesoamerica, Mazahua and Zapotec. All newly sequenced mitogenomes could be classified into haplogroups A2, B2, C1 and D1, but one sequence in Mazahua was D4h3a, a subclade of haplogroup D4. This haplogroup has been mostly found in South America along the Pacific coast. Haplogroup X2a was not found in either population. Genetic similarity obtained using phylogenetic tree construction and principal component analysis showed that these two populations are distantly related to each other. Actually, the Mazahua and the Zapotec shared no sequences (haplotypes) in common, while each also showed a number of unique subclades. Surprisingly, Zapotec formed a cluster with indigenous populations living in an area from central Mesoamerica to Central America. By contrast, the Mazahua formed a group with indigenous populations living in external areas, including southwestern North America and South America. This intriguing genetic relationship suggests the presence of two paleo-Mesoamerican groups, invoking a scenario in which one group had expanded into South America and the other resided in Mesoamerica.