Oncolytic viruses (OVs) comprise a versatile and multi-mechanistic therapeutic platform in the growing arsenal of anticancer biologics. These replicating therapeutics find favorable conditions in the tumor niche, characterized among others by increased metabolism, reduced anti-tumor/antiviral immunity, and disorganized vasculature. Through a self-amplification that is dependent on multiple cancer-specific defects, these agents exhibit remarkable tumor selectivity. With several OVs completing or entering Phase III clinical evaluation, their therapeutic potential as well as the challenges ahead are increasingly clear. One key hurdle is tumor heterogeneity, which results in variations in the ability of tumors to support productive infection by OVs and to induce adaptive anti-tumor immunity. To this end, mounting evidence suggests tumor epigenetics may play a key role. This review will focus on the epigenetic landscape of tumors and how it relates to OV infection. Therapeutic strategies aiming to exploit the epigenetic identity of tumors in order to improve OV therapy are also discussed.