Currently, few prognostic factors are available to predict the emergence of castration-resistant prostate cancer and no curative options are available. Epigenetic gene regulation has been shown to trigger prostate cancer metastasis and androgen independence. Histone lysine demethylases (KDMs) are epigenetic enzymes that can remove both repressive and activating histone marks. KDM5 family members are capable of removing the histone H3 lysine 4 dimethylation–activating mark, rendering them potential players in the down-regulation of tumor suppressors and suggesting that their activity could repress oncogenes. Here, we systematically investigated KDM5C expression patterns in two independent radical prostatectomy cohorts (822 prostate tumors in total) by immunohistochemistry. Positive nuclear KDM5C staining was significantly associated with a reduced prostate-specific antigen relapse-free survival. Our study confirmed that nuclear KDM5C expression is an independent prognostic parameter. Most strikingly, the prognostic value of nuclear KDM5C expression for progression-free survival was exclusively pronounced for the Gleason group 7. In addition, KDM5C knockdown resulted in growth retardation of prostate cancer cells in vitro and induced regulation of several proliferation-associated genes. Our data indicate that KDM5C is functionally involved in proliferation control of prostate cancer cells and might represent a novel attractive therapy target. Moreover, overexpression of KDM5C is an independent new predictive marker for therapy failure as determined by biochemical recurrence in patients after prostatectomy.