The growth of immunogenic tumors in immunocompetent individuals is one of the oldest conundrums in tumor immunology. Although the ability of mouse CD8+ T cells to control transplanted tumors is well documented, little is known about their impact on autochthonous tumors. To gain insight into the role of CD8+ T cells during the course of cancer development, we produced a novel model of spontaneous melanoma. The metallothionein (MT)-ret/AAD mouse is transgenic for the RET oncogene and the chimeric MHC molecule AAD (α 1-α 2 domains of HLA-A2 linked to α 3 domain of H2-D d). This model recapitulates the natural history of human melanoma, and expression of the AAD molecule makes it suitable for analyzing CD8+ T cell responses directed against peptide Ags that have been previously identified in HLA-A2+ melanoma patients. We found that, as tumors grow, mice develop a broad melanoma-specific CD8+ T cell response. Occurrence of cutaneous nodules is not affected by CD8+ T cell depletion, showing that although CD8+ T cells are functional, they have no effect on established cutaneous tumors. However, depleted mice die from visceral disease much earlier than controls, showing that CD8+ T cells control metastasis spreading and disease progression. Antigenic modulation is observed in visceral metastases, suggesting that visceral nodules may be subject to immunoediting. Our data demonstrate that growth of melanoma in the MT-ret/AAD model involves several tolerance mechanisms sequentially. They also reveal a different role for CD8+ T cells toward early stage of cutaneous tumors and late visceral metastatic stage of the disease.