The polycomb group (PcG) genes encode a family of proteins that methylate and ubiquitinate histones to close chromatin and suppress gene expression. PcG proteins are present at elevated levels in cancer cells, and this is associated with reduced tumor suppressor protein level and enhanced cell survival. Agents that reduce PcG protein level are regarded as potentially cancer-preventative agents. Sulforaphane (SFN) is a biologically important isothiocyanate found in cruciferous vegetables that is an important candidate chemopreventive agent. However, the impact of SFN on the level and function of PcG proteins in skin cancer cells has not been assessed. We show that SFN treatment causes a concentration-dependent reduction in PcG protein (Bmi-1, Ezh2) expression in SCC-13 skin cancer cells and also reduces trimethylation of lysine 27 of histone H3. This is associated with accumulation of cells in G(2)/M phase; reduced levels of cyclin B1, cyclin A, cyclin dependent kinases 1 and 2; and increased p21(Cip1) expression. Sulforaphane treatment also increases cleavage of procaspase 3, 8, and 9 and enhances PARP cleavage and apoptosis. Similar results are observed in other skin-derived cell immortalized and transformed cell lines. Forced expression of the Bmi-1 polycomb protein in SCC-13 cells reverses these effects. The SFN-dependent loss of Bmi-1 and Ezh2 is due to proteasome-associated degradation. These results suggest that dietary isothiocyanates may suppress cancer progression by reducing PcG protein level via a proteasome-dependent mechanism, thereby inhibiting PcG-dependent pro-survival epigenetic events.