The Epstein-Barr virus (EBV) is one of the predominant tumor viruses in humans, but so far no therapeutic or prophylactic vaccination against this transforming pathogen is available. We demonstrated that heterologous prime-boost vaccination with the nuclear antigen 1 of EBV (EBNA1), either targeted to the DEC205 receptor on DCs or expressed from a recombinant modified vaccinia virus Ankara (MVA) vector, improved priming of antigen-specific CD4+ T cell help. This help supported the expansion and maintenance of EBNA1-specific CD8+ T cells that are most efficiently primed by recombinant adenoviruses that encode EBNA1. These combined CD4+ and CD8+ T cell responses protected against EBNA1-expressing T and B cell lymphomas, including lymphoproliferations that emerged spontaneously after EBNA1 expression. In particular, the heterologous EBNA1-expressing adenovirus, boosted by EBNA1-encoding MVA vaccination, demonstrated protection as a prophylactic and therapeutic treatment for the respective lymphoma challenges. Our study shows that such heterologous prime-boost vaccinations against EBV-associated malignancies as well as symptomatic primary EBV infection should be further explored for clinical development.