Mexico is a rich source for anthropological and population genetic studies with high diversity in ethnic and linguistic groups. The country witnessed the rise and fall of major civilizations, including the Maya and Aztec, but resulting from European colonization, the population landscape has dramatically changed. Today, the majority of Mexicans do not identify themselves as Indigenous but as admixed, and appear to have very little in common with their pre-Columbian predecessors. However, when the maternally inherited mitochondrial (mt)DNA is investigated in the modern Mexican population, this is not the case. Control region sequences of 2021 samples deriving from all over the country revealed an overwhelming Indigenous American legacy, with almost 90% of mtDNAs belonging to the four major pan-American haplogroups A2, B2, C1, and D1. This finding supports a very low European contribution to the Mexican gene pool by female colonizers and confirms the effectiveness of employing uniparental markers as a tool to reconstruct a country’s history. In addition, the distinct frequency and dispersal patterns of Indigenous American and West Eurasian clades highlight the benefit such large and country-wide databases provide for studying the impact of colonialism from a female perspective and population stratification. The importance of geographical database subsets not only for forensic application is clearly demonstrated.