Histone deacetylase inhibitors (HDACi) are a novel class of anti-cancer agents that potently induce tumour cell-specific apoptosis. HDACi can also enhance tumour cell immunogenicity in vitro and promote engagement of immune effector mechanisms that may contribute to the anti-tumor activities of the compounds. However the effect of HDACi treatment on the generation of anti-tumour immunity in vivo is less well understood. We therefore utilized pre-clinical, syngeneic murine models of cancer to investigate the role of the immune system in mediating the anti-cancer effects of HDACi. We demonstrated treatment of established myc-driven lymphoma with the HDACi vorinostat was dramatically less efficacious in mice lacking functional lymphocytes compared to wild-type mice. Immunocompromised mice succumbed to lymphoma significantly earlier than wild-type mice and did not display overt signs of toxicity or resistance to HDACi treatment. Similar results were obtained utilizing the HDACi panobinostat or a genetically different lymphoma. Importantly, the conventional chemotherapeutic drug etoposide was able to control lymphoma in both immunocompetent and immunocompromised mice. Investigation into the immune effector mechanism underpinning the therapeutic efficacy of HDACi revealed a critical role for host production of IFN-γ that was acting on the tumor and not host tissue. Further examination suggested HDACi and IFN-γ were acting in concert to enhance the expression of MHC class I and II on lymphoma cells, thereby enhancing the immunogenicity of tumour cells in vivo and potentially promoting tumour eradication by immune effector cells. In line with this, treatment of established lymphoma with HDACi in combination with the IFN-γ-inducing adjuvant α-Galactosylceramide was significantly more effective than either agent alone. Together these novel data suggest an intact immune system is required to mediate the anti-cancer effects of HDACi and that the rational combination of HDACi with immune-stimulating therapy may be highly beneficial for the treatment of established cancer.