Cancer vaccines targeting 'self' antigens that are expressed at consistently high levels by tumor cells are potentially useful in immunotherapy, but immunological tolerance may block their function. Here, we describe a novel, naked DNA vaccine encoding an alphavirus replicon (self-replicating mRNA) and the self/tumor antigen tyrosinase-related protein-1. Unlike conventional DNA vaccines, this vaccine can break tolerance and provide immunity to melanoma. The vaccine mediates production of double-stranded RNA, as evidenced by the autophosphorylation of dsRNA-dependent protein kinase R (PKR). Double-stranded RNA is critical to vaccine function because both the immunogenicity and the anti-tumor activity of the vaccine are blocked in mice deficient for the RNase L enzyme, a key component of the 2′,5′-linked oligoadenylate synthetase antiviral pathway involved in double-stranded RNA recognition. This study shows for the first time that alphaviral replicon-encoding DNA vaccines activate innate immune pathways known to drive antiviral immune responses, and points the way to strategies for improving the efficacy of immunization with naked DNA.