Active vaccination strategies using viral vectors often give disappointing protection from tumor development, and usually require multiple immunizations. These approaches normally use viruses that cause acute infections, as they provoke potent CD8 T cell responses. Persistent virus vectors have not been used in this setting due to the perception that exhaustion of the T cell response occurs and would lead to poor anti-tumor protection. However, such exhaustion generally only occurs in high-load virus infections, whereas T cell function is intact in lower-load persistent infections. In fact, CD8 T cell responses in these infections, which are adapted for long-term immune surveillance, have properties that may make them more desirable for long-term anti-tumor immunity. In this report, we show that a persistent gammaherpesvirus vector provides superior protection against melanoma, relative to a non-persistent mutant of the same virus. These data suggest that vaccine vectors derived from persistent viruses may perform better than those from acute viruses at mediating anti-tumor protection.