Understanding immune mechanisms influencing cancer regression, recurrence, and metastasis may be critical to developing effective immunotherapy. Using a tumor expressing HIV gp160 as a model viral tumor Ag, we found a growth-regression-recurrence pattern, and used this to investigate mechanisms of immunosurveillance. Regression was dependent on CD8 T cells, and recurrent tumors were resistant to CTL, had substantially reduced expression of epitope mRNA, but retained the gp160 gene, MHC, and processing apparatus. Increasing CTL numbers by advance priming with vaccinia virus expressing gp160 prevented only the initial tumor growth but not the later appearance of escape variants. Unexpectedly, CD4 cell depletion protected mice from tumor recurrence, whereas IL-4 knockout mice, deficient in Th2 cells, did not show this protection, and IFN-gamma knockout mice were more susceptible. Purified CD8 T cells from CD4-depleted mice following tumor regression had more IFN-gamma mRNA and lysed tumor cells without stimulation ex vivo, in contrast to CD4-intact mice. Thus, the quality as well as quantity of CD8+ CTL determines the completeness of immunosurveillance and is controlled by CD4 T cells but not solely Th2 cytokines. This model of immunosurveillance may indicate ways to enhance the efficacy of surveillance and improve immunotherapy.