Anti-tumor vaccination is being evaluated as a prophylactic and therapeutic strategy against cancer growth, dissemination (spreading) or recurrence. Although a large number of studies investigate in detail the identity of antigens to be used for efficacious immune intervention, there have been few studies investigating the optimal form for antigen to be used in the vaccine. Here we show in a mouse H-2(d) MHC background and for NY-ESO-1 that genetic (plasmid DNA) but not full length protein vaccine is capable of inducing a protective prophylactic anti-tumor cytotoxic T-cell immune response in vivo. Peptide vaccination using nominal MHC class I epitope adjuvanted with a Toll Like Receptor agonist such as stabilized RNA can also provide some anti-tumor protection. Our results highlight the idea that when evaluating the clinical efficacy of a cancer vaccine, not only the identity of the antigen but also the format of the vaccine is of the utmost importance.