Physical performance is a multifactorial and complex trait influenced by environmental and hereditary factors. Environmental factors alone have been insufficient to characterize all outstanding phenotypes. Recent advances in genomic technologies have enabled the investigation of whole nuclear and mitochondrial genome sequences, increasing our ability to understand interindividual variability in physical performance. Our objective was to evaluate the association of mitochondrial polymorphic loci with physical performance in Brazilian elite military personnel. Eighty-eight male military personnel who participated in the Command Actions Course of the Army were selected. Total DNA was obtained from blood samples and a complete mitochondrial genome (mtDNA) was sequenced using Illumina MiSeq platform. Twenty-nine subjects completed the training program (FINISHED, 'F'), and fifty-nine failed to complete (NOT_FINISHED, 'NF'). The mtDNA from NF was slightly more similar to genomes from African countries frequently related to endurance level. Twenty-two distinct mtDNA haplogroups were identified corroborating the intense genetic admixture of the Brazilian population, but their distribution was similar between the two groups (FST=0.0009). Of 745 polymorphisms detected in the mtDNA, the position G11914A within the NADPH gene component of the electron transport chain, was statistically different between F and NF groups (P=0.011; OR: 4.286; 95%CI: 1.198-16.719), with a higher frequency of the G allele in group F individuals). The high performance of military personnel may be mediated by performance-related genomic traits. Thus, mitochondrial genetic markers such as the ND4 gene may play an important role on physical performance variability.