Prostate cancer (PCa) is a very common neoplasm, which is generally treated by chemo-, radio-, and/or hormonal-therapy. After a variable time, PCa becomes resistant to conventional treatment, leading to patient death. Prostate tumor-initiating cells (TICs) and cancer repopulating cells (CRCs) are stem-like populations, driving respectively cancer initiation and progression. Histone modifiers (HMs) control gene expression in normal and cancer cells, thereby orchestrating key physiological and pathological processes. In particular, Polycomb group genes (PcGs) are a set of HMs crucial for lineage-specific gene silencing and stem cell self renewal. PcG products are organized into two main Polycomb Repressive Complexes (PRCs). At specific loci, PRC2 catalyzes histone H3 Lys27 trimethylation, which triggers gene silencing by recruiting PRC1, histone deacetylases and DNA methyl transferases. PRC1 catalyzes addition of the repressive mark histone H2A ubiquitination. Recently, the catalytic component of PRC1 (BMI1) was shown to play critical roles in prostate CRC self-renewal and resistance to chemotherapy, resulting in poorer prognosis. Similarly, pharmacological disruption of PRC2 by a small molecule inhibitor reduced the tumorigenicity and metastatic potential of prostate CRCs. Along with PcGs, some histone lysine demethylases (KDMs) are emerging as critical regulators of TIC/CRC biology. KDMs may be inhibited by specific small molecules, some of which display antitumor activity in PCa cells at micromolar concentrations. Since epigenetic gene regulation is crucial for stem cell biology, exploring the role of HMs in prostate cancer is a promising path that may lead to novel treatments.