Background: Taenia solium is a parasite of public health concern, causing human taeniasis and cysticercosis. Two main genotypes have been identified: Asian and African-American. Although characterizing T. solium genotypes is crucial to understanding the genetic epidemiology of its diseases, not much is known about the differences between T. solium mitochondrial genomes from different genotypes. Also, little is known about whether genotypes are further subdivided. Therefore, this study aimed to identify a set of point mutations distributed throughout the T. solium mitochondrial genome that differentiate the African-American from the Asian genotype. Another objective was to identify whether T. solium main genotypes are further stratified. Methods: One Mexican and two Peruvian T. solium mitochondrial genomes were assembled using reads available in the NCBI Sequence Read Archive and the reference genome from China as a template. Mutations with respect to the Chinese reference were identified by multiple genome alignment. Jensen–Shannon and Grantham scores were computed for mutations in protein-coding genes to evaluate whether they affected protein function. Phylogenies by Bayesian inference and haplotype networks were constructed using cytochrome c oxidase subunit 1 and cytochrome b from these genomes and other isolates to infer phylogeographical relationships. Results: A set of 31 novel non-synonymous point mutations present in all genomes of the African-American genotype were identified. These mutations were distributed across the mitochondrial genome, differentiating the African-American from the Asian genotype. All occurred in non-conserved protein positions. Furthermore, the analysis suggested a stratification of the African-American genotypes into an East African and a West African sublineage. Conclusions: A novel set of 31 non-synonymous mutations differentiating the main T. solium genotypes was identified. None of these seem to be causing differences in mitochondrial protein function between parasites of the two genotypes. Furthermore, two sublineages within the African-American genotype are proposed for the first time. The presence of the East African sublineage in the Americas suggests an underestimated connection between East African and Latin American countries that might have arisen in the major slave trade between Portuguese Mozambique and the Americas. The results obtained here help to complete the molecular epidemiology of the parasite.