Prostate cancer is one of the most frequent cancers in males in Western industrialized countries. Its course is highly variable, from indolent to highly lethal. Genetic changes vary accordingly, with chromosomal losses, gains and translocations, although often recurrent, differing between individual cases of the disease. In contrast, certain epigenetic changes are highly consistent, in particular hypermethylation of a specific set of genes, and others regularly associated with progression, such as global DNA hypomethylation, certain chromatin modifications and altered levels and composition of polycomb complexes. Although changes in polycombs and DNA methylation appear to both accompany the progression of prostate cancer, recent studies do not suggest that they cause one another. However, they may contribute to establishing and maintaining an aberrant differentiation potential of prostate cancer initiating cells. Global DNA hypomethylation in prostate cancer may relate to adaptative changes in several signaling pathways typical of this cancer type, including innate immunity responses. Similarly, adaptative changes in the expression and function of chromatin regulators required to diminish the dependency of prostate cancer cells on androgens may shape the epigenome, beyond individual genes regulated by the androgen receptor. Because of their crucial role, epigenetic alterations may become highly useful for diagnostics and therapy of prostate cancer.