Prostate cancer (PCa) has a broad spectrum of clinical behavior; hence, biomarkers are urgently needed for risk stratification. Here, we aim to find potential biomarkers for risk stratification, by utilizing a gene co-expression network of transcriptomics data in addition to laser-microdissected proteomics from human and murine prostate FFPE samples. We show up-regulation of oxidative phosphorylation (OXPHOS) in PCa on the transcriptomic level and up-regulation of the TCA cycle/OXPHOS on the proteomic level, which is inversely correlated to STAT3 expression. We hereby identify gene expression of pyruvate dehydrogenase kinase 4 (PDK4), a key regulator of the TCA cycle, as a promising independent prognostic marker in PCa. PDK4 predicts disease recurrence independent of diagnostic risk factors such as grading, staging, and PSA level. Therefore, low PDK4 is a promising marker for PCa with dismal prognosis.