Cancer cells are under the surveillance of the host immune system. Nevertheless, a number of immunosuppressive mechanisms allow tumors to escape protective responses and impose immune tolerance. Epigenetic alterations are central to cancer cell biology and cancer immune evasion. Accordingly, epigenetic modulating agents (EMAs) are being exploited as anti-neoplastic and immunomodulatory agents to restore immunological fitness. By simultaneously acting on cancer cells, e.g. by changing expression of tumor antigens, immune checkpoints, chemokines or innate defense pathways, and on immune cells, e.g. by remodeling the tumor stroma or enhancing effector cell functionality, EMAs can indeed overcome peripheral tolerance to transformed cells. Therefore, combinations of EMAs with chemo- or immunotherapy have become interesting strategies to fight cancer. Here we review several examples of epigenetic changes critical for immune cell functions and tumor-immune evasion and of the use of EMAs in promoting anti-tumor immunity. Finally, we provide our perspective on how EMAs could represent a game changer for combinatorial therapies and the clinical management of cancer.