Switching of cellular energy production from oxidative phosphorylation (OXPHOS) to aerobic glycolysis occurs in many types of tumors. However, the significance of energy metabolism for the development of prostate carcinoma is poorly understood. We investigated the expression of OXPHOS complexes in 94 human prostate carcinomas and paired benign tissue using immunohistochemistry. Overall mitochondrial mass was upregulated in carcinomas compared to benign prostate tissue in all Gleason grades. A significant direct correlation between the expression of OXPHOS complexes I, II, and V and the Gleason score was observed. However, 17% of prostate carcinomas and 18% of benign prostate tissues showed isolated or combined deficiency of OXPHOS complexes (one deficiency in 12% of the tumors, combined deficiencies in 5%). Complex I was absent in 9% of the samples, with only parts of the tumor affected. ATP5F1A, a complex V protein, was the most frequently affected subunit, in 10% of tumors and 11% of benign prostate tissues (but not both tissues in any single patient). A possible role of complex V in prostate cancer development is suggested by the significant positive correlation of ATP5F1A levels with earlier-onset prostate cancer (age at diagnosis and at prostatectomy) and free PSA percentage. The relatively high percentage (17%) of prostate carcinomas with regional foci of partial OXPHOS complex deficiencies could have important therapeutic implications.