The ability of cancer cells to divide indefinitely whilst supporting tumor growth, metastasis and invasiveness resembles the behavior of stem cells. Here, we overview the role of Polycomb (PcG)-dependent epigenetic silencing mechanisms in stem cell biology and cancer, focusing on two major PcG components, Ezh2 and Bmi1. In a recent patent, stem cell PcG targets were shown to be more prone to cancer-specific promoter DNA methylation than non-targets, indicating that reversible PcG-mediated gene repression becomes replaced by permanent silencing. This epigenetic switching keeps the cell in a sustained state of self-renewal, predisposing it to tumorigenic transformation. These findings might provide the means of identifying the stem-cell epigenetic signatures associated with the origin of specific types of cancer. Based on the reversibility of epigenetic histone modifications, PcG proteins have become established targets in clinical practice for the treatment of a variety of cancers, notably treatments with histone deacetylase and methyltransferase inhibitors. A number of reports and patents highlight the potential of alternative approaches to targeting PcG for cancer therapy, including micro-RNA expression and the use of Hedgehog signaling pathway antagonists. The major shortcoming of current approaches is their lack of specificity. The identification of tumorigenic epigenetic alterations together with the development of inhibitors to target them promises to open the way toward personalized cancer treatment.