APOBEC3B, an anti-viral cytidine deaminase which induces DNA mutations, has been implicated as a mediator of cancer evolution and therapeutic resistance. Mutational plasticity also drives generation of neoepitopes, which prime anti-tumor T cells. Here, we show that overexpression of APOBEC3B in tumors increases resistance to chemotherapy, but simultaneously heightens sensitivity to immune checkpoint blockade in a murine model of melanoma. However, in the vaccine setting, APOBEC3B-mediated mutations reproducibly generate heteroclitic neoepitopes in vaccine cells which activate de novo T cell responses. These cross react against parental, unmodified tumors and lead to a high rate of cures in both subcutaneous and intra-cranial tumor models. Heteroclitic Epitope Activated Therapy (HEAT) dispenses with the need to identify patient specific neoepitopes and tumor reactive T cells ex vivo. Thus, actively driving a high mutational load in tumor cell vaccines increases their immunogenicity to drive anti-tumor therapy in combination with immune checkpoint blockade.