It has been proposed that cancer prevention results from multiple dietary agents acting together as “action packages.” Here we obtain evidence that butyrate, which is generated from dietary fiber, enhances the responsiveness of colon cancer cells to all-trans retinoic acid (ATRA). Evidence was obtained that this interaction depends on histone deactylase one (HDAC1) inhibition by butyrate and retinoic acid receptor alpha (RARα) activation by ATRA. The enhancement of RAR beta 2 (RARβ2) activation was accompanied by a rapid demethylation of the RARβ2 promoter. This demethylation could be achieved by butyrate alone, and it differed from that triggered by the DNA methyltransferase inhibitor 5-Aza-2′ deoxycytidine in that it was 1) sporadic on the RARβ2 promoter, 2) not genome wide, and 3) independent of extensive DNA replication. An analysis of inter-methylated sites assay indicated that only a few percent of loci analyzed showed reduced methylation. In colon cancer cells that were particularly resistant to RARβ2 reactivation, the actions of butyrate could be further enhanced by the soy isoflavone genistein, which has also been reported to work through an epigenetic mechanism. These data suggest that dietary compounds that modulate epigenetic programming are likely to function best in the presence of retinoids and other cancer-preventing compounds that are sensitive to a cell's epigenetic state.