The development of therapeutic strategies which induce effective cellular antitumor immunity represents an important goal in cancer immunology. Here, we used the unique features of the genetically engineered Hgf-Cdk4(R24C) mouse model to identify a combination chemoimmunotherapy for melanoma. These mice develop primary cutaneous melanomas which grow progressively and metastasize in the absence of immunogenic foreign proteins such as oncogenes or antigens. Primary and metastatic tumors evade innate and adaptive immune defenses, although they naturally express melanocytic antigens which can be recognized by antigen-specific T cells. We found that primary melanomas continued to grow despite infiltration with adoptively transferred, in vivo-activated, tumor-specific CD8(+) T cells. To promote tumor immune defense, we developed a treatment protocol consisting of four complementary components: (a) chemotherapeutic preconditioning prior to (b) adoptive lymphocyte transfer and (c) viral vaccination followed by (d) adjuvant peritumoral injections of immunostimulatory nucleic acids. Lymphocyte ablation and innate antiviral immune stimulation cooperatively enhanced the expansion and the effector cell differentiation of adoptively transferred lymphocytes. The efficacy of the different treatment approaches converged in the tumor microenvironment and induced a strong cytotoxic inflammatory response enabling preferential recognition and destruction of melanoma cells. This combination chemoimmunotherapy caused complete regression of advanced primary melanomas in the skin and metastases in the lung with minimal autoimmune side effects. Our results in a clinically highly relevant experimental model provide a scientific rationale to evaluate similar strategies which unleash the power of innate and adaptive immune defense in future clinical trials.