Cancer vaccine that targets 'self'-antigens expressed at high levels in tumor cells is a potentially useful immunotherapy, but immunological tolerance often defeats this strategy. Here, we describe the use of a naked DNA vaccine encoding a self tumor antigen, tyrosinase-related protein 2, to whose N-terminus ubiquitin is fused in a 'nonremovable' fashion. Unlike conventional DNA vaccines, this vaccine broke the tolerance and induced protective immunity to melanoma in C57BL/6 mice, as evaluated by tumor growth, survival rate and lung metastasis. The protective immunity was cancelled in the proteasome activator PA28alpha/beta knockout mice. Moreover, this vaccination exhibited therapeutic effects on melanoma implanted before vaccination. Our findings provide evidence for the first time that naked DNA vaccines encoding a ubiquitin-fused self-antigen preferentially induce the main effector CD8+ T cells through efficient proteolysis mediated by the ubiquitin-proteasome pathway, and lead the way to strategies aimed at targeting tissue differentiation antigens expressed by tumors.