We have investigated the therapeutic potential of a prototypic melanoma vaccine based on recombinant adenovirus expressing human dopachrome tautomerase in the B16F10 murine melanoma model. We found that in the presence of a tumor, the magnitude of T-cell immunity evoked by the vaccine was significantly reduced. This impairment was compounded by defects in cytokine production and degranulation within the tumor-infiltrating lymphocytes (TILs). We showed that the combination of vaccination with high-dose cyclophosphamide was able to skew the response toward the target antigen and enhanced both the quantity and quality of antigen-specific CD8+ and CD4+ T-cell responses in tumor-bearing mice, which resulted in the inhibition of tumor growth. Furthermore, when tumor-specific antigens were targeted by the vaccine, the combination therapy could actually produce tumor regression, which appeared to result from the high frequency of antigen-specific T cells. These data show that recombinant adenovirus vaccines are compatible with conventional high-dose chemotherapy and that the combined treatment results in improved therapeutic outcomes relative to either agent individually.