Harnessing the immune system to eradicate tumors requires identification and targeting of tumor antigens, including tumor-specific neoantigens and tumor-associated self-antigens. Tumor-associated antigens are subject to existing immune tolerance, which must be overcome by immunotherapies. Despite many novel immunotherapies reaching clinical trials, inducing self-antigen-specific immune responses remains challenging. Here, we systematically investigate viral-vector-based cancer vaccines encoding a tumor-associated self-antigen (TRP2) for the treatment of established melanomas in preclinical mouse models, alone or in combination with adoptive T cell therapy. We reveal that, unlike foreign antigens, tumor-associated antigens require replication of lymphocytic choriomeningitis virus (LCMV)-based vectors to break tolerance and induce effective antigen-specific CD8+ T cell responses. Immunization with a replicating LCMV vector leads to complete tumor rejection when combined with adoptive TRP2-specific T cell transfer. Importantly, immunization with replicating vectors leads to extended antigen persistence in secondary lymphoid organs, resulting in efficient T cell priming, which renders previously “cold” tumors open to immune infiltration and reprograms the tumor microenvironment to “hot.” Our findings have important implications for the design of next-generation immunotherapies targeting solid cancers utilizing viral vectors and adoptive cell transfer.