Dietary intake of bioactive phytochemicals including the cruciferous vegetable derivative phenethyl isothiocyanate (PEITC) can reduce risk of human cancers, but possible epigenetic mechanisms of these effects are yet unknown. We therefore sought to identify the molecular basis of PEITC-mediated epigenetic tumor restriction. Colon cancer cells treated with low-dose PEITC for >1 month exhibited stable alterations in expression profile of epigenetic writers/erasers and chromatin-binding of histone deacetylases (HDACs) and Polycomb-group (PcG) proteins. Sustained PEITC exposure not only blocked HDAC binding to euchromatin but was also associated with hypomethylation of PcG target genes that are typically hypermethylated in cancer. Furthermore, PEITC treatment induced expression of pro-Apoptotic genes in tumor cells, which was partially reversed by overexpression of PcG member BMI-1, suggesting opposing roles for PEITC and PcG proteins in control of tumor progression. These data demonstrate that PEITC regulates chromatin binding of key epigenetic writers/erasers and PcG complexes to restrict tumor development.