In embryonic stem cells, promoters of key lineage-specific differentiation genes are found in a bivalent state, having both activating H3K4me3 and repressive H3K27me3 histone marks, making them poised for transcription upon loss of H3K27me3. Whether cancer-initiating cells (C-ICs) have similar epigenetic mechanisms that prevent lineage commitment is unknown. Here we show that colorectal C-ICs (CC-ICs) are maintained in a stem-like state through a bivalent epigenetic mechanism. Disruption of the bivalent state through inhibition of the H3K27 methyltransferase EZH2, resulted in decreased self-renewal of patient-derived C-ICs. Epigenomic analyses revealed that the promoter of Indian Hedgehog (IHH), a canonical driver of normal colonocyte differentiation, exists in a bivalent chromatin state. Inhibition of EZH2 resulted in de-repression of IHH, decreased self-renewal, and increased sensitivity to chemotherapy in vivo. Our results reveal an epigenetic block to differentiation in CC-ICs and demonstrate the potential for epigenetic differentiation therapy of a solid tumour through EZH2 inhibition.