Prostate cancer management is complicated by extreme disease heterogeneity, which is further limited by availability of prognostic biomarkers. Recognition of prostate cancer as a genetic disease has prompted a focus on the nuclear genome for biomarker discovery, with little attention given to the mitochondrial genome. While it is evident that mitochondrial DNA (mtDNA) mutations are acquired during prostate tumorigenesis, no study has evaluated the prognostic value of mtDNA variation. Here we used next-generation sequencing to interrogate the mitochondrial genomes from prostate tissue biopsies and matched blood of 115 men having undergone a radical prostatectomy for which there was a mean of 107 months clinical follow-up. We identified 74 unique prostate cancer specific somatic mtDNA variants in 50 patients, providing significant expansion to the growing catalog of prostate cancer mtDNA mutations. While no single variant or variant cluster showed recurrence across multiple patients, we observe a significant positive correlation between the total burden of acquired mtDNA variation and elevated Gleason Score at diagnosis and biochemical relapse. We add to accumulating evidence that total acquired genomic burden, rather than specific mtDNA mutations, has diagnostic value. This is the first study to demonstrate the prognostic potential of mtDNA mutational burden in prostate cancer.