Therapeutic vaccination regimens inducing clinically effective tumor-specific CD8+ T lymphocyte (CTL) responses are an unmet medical need. We engineer two distantly related arenaviruses, Pichinde virus and lymphocytic choriomeningitis virus, for therapeutic cancer vaccination. In mice, life-replicating vector formats of these two viruses delivering a self-antigen in a heterologous prime-boost regimen induce tumor-specific CTL responses up to 50% of the circulating CD8 T cell pool. This CTL attack eliminates established solid tumors in a significant proportion of animals, accompanied by protection against tumor rechallenge. The magnitude of CTL responses is alarmin driven and requires combining two genealogically distantly related arenaviruses. Vector-neutralizing antibodies do not inhibit booster immunizations by the same vector or by closely related vectors. Rather, CTL immunodominance hierarchies favor vector backbone-targeted responses at the expense of self-reactive CTLs. These findings establish an arenavirus-based immunotherapy regimen that allows reshuffling of immunodominance hierarchies and breaking self-directed tolerance for efficient tumor control.