Declines in walking speed are associated with a variety of poor health outcomes including disability, comorbidity, and mortality. While genetic factors are putative contributors to variability in walking, few genetic loci have been identified for this trait. We examined the role of mitochondrial genomic variation on walking speed by sequencing the entire mitochondrial DNA (mtDNA). Data were meta-analyzed from 1758 Lifestyle Interventions and Independence for Elders (LIFE) Study and replication data from 730 Health, Aging, and Body Composition (HABC) Study participants with baseline walking speed information. Participants were 69+ years old of diverse racial backgrounds (African, European, and other race/ethnic groups) and had a wide range of mean walking speeds [4–6 m (0.78–1.09 m/s) and 400 m (0.83–1.24 m/s)]. Meta-analysis across studies and racial groups showed that m.12705C>T, ND5 variant was significantly associated (p < 0.0001) with walking speed at both short and long distances. Replication and meta-analysis also identified statistically significant walking speed associations (p < 0.0001) between the m.5460.G>A, ND2 and m.309C>CT, HV2 variants at short and long distances, respectively. All results remained statistically significant after multiple comparisons adjustment for 499 mtDNA variants. The m.12705C>T variant can be traced to the beginnings of human global migration and that cells carrying this variant display altered tRNA expression. Significant pooled effects related to stopping during the long-distance walk test were observed across OXPHOS complexes I (p = 0.0017) and III (p = 0.0048). These results suggest that mtDNA-encoded variants are associated with differences in walking speed among older adults, potentially identifying those at risk of developing mobility impairments.