Background: Epigenetic alterations are common in prostate cancer, yet how these modifications contribute to carcinogenesis is poorly understood. We investigated whether specific histone modifications are prognostic for prostate cancer relapse, and whether the expression of epigenetic genes is altered in prostate tumorigenesis. Methods: Global levels of histone H3 lysine-18 acetylation (H3K18Ac) and histone H3 lysine-4 dimethylation (H3K4diMe) were assessed immunohistochemically in a prostate cancer cohort of 279 cases. Epigenetic gene expression was investigated in silico by analysis of microarray data from 23 primary prostate cancers (8 with biochemical recurrence and 15 without) and 7 metastatic lesions. Results: H3K18Ac and H3K4diMe are independent predictors of relapse-free survival, with high global levels associated with a 1.71-fold (P < 0.0001) and 1.80-fold (P = 0.006) increased risk of tumor recurrence, respectively. High levels of both histone modifications were associated with a 3-fold increased risk of relapse (P < 0.0001). Epigenetic gene expression profiling identified a candidate gene signature (DNMT3A, MBD4, MLL2, MLL3, NSD1, and SRCAP), which significantly discriminated nonmalignant from prostate tumor tissue (P = 0.0063) in an independent cohort. Conclusions: This study has established the importance of histone modifications in predicting prostate cancer relapse and has identified an epigenetic gene signature associated with prostate tumorigenesis. Impact: Our findings suggest that targeting the epigenetic enzymes specifically involved in a particular solid tumor may be a more effective approach. Moreover, testing for aberrant expression of epigenetic genes such as those identified in this study may be beneficial in predicting individual patient response to epigenetic therapies.