The generation of protective CD8 T-cell memory against tumor-expressed self-antigens is an important but elusive goal of cancer immunotherapy. The possibility that a progressive, poorly immunogenic tumor can induce T-cell memory against self-antigens has not previously been studied. Herein, we report that growth of the poorly immunogenic B16 melanoma in the absence of regulatory T cells (T_reg) generates CD8 T-cell responses that develop into functional memory after the tumor has been surgically excised. Tumor-primed memory T cells recognized melanocyte differentiation antigens TRP-2/DCT and gp100 and persisted for as long as 5 months following surgical tumor excision. Phenotypic analysis showed that these cells develop into both central and effector memory T-cell subsets, which produce IFN-γ and interleukin-2 on reencounter with antigen. Most importantly, tumor-primed memory T cells mediated the rejection of intradermal and systemically disseminated challenge tumors given 30 to 60 days following surgery. Tumor-excised mice also developed autoimmune vitiligo, showing that T_reg cells prevent tissue-specific autoimmunity in tumor-bearing hosts. This study establishes that T_reg depletion in tumor-bearing hosts drives the natural development of protective T-cell memory. Generating such responses may aid in the clinical management of tumor recurrence and metastasis following surgery. [Cancer Res 2007;67(13):6468–76]