Immunization with an adenovirus-PSA (Ad5-PSA) vaccine alone strongly induces the expansion of CD8+ T cells with enhanced cytotoxic T lymphocyte (CTL) activity against the antigen-bearing tumor cells in vitro as well as in vivo in a mouse model of prostate cancer. However, in an attempt to enhance the anti-tumor immunity induced by the vaccine, co-administration of CpG oligodeoxynucleotides (CpG ODN) with Ad5-PSA vaccine dramatically reduces the immune responses measured by in vitro CTL activity and the number of IFN-gamma producing cells. Surprisingly, in vivo experiments showed that mice immunized with the combined approach of Ad5-PSA and CpG had enhanced protection against the subsequent tumor challenge as compared to mice immunized with vaccine alone. These data demonstrate an unexpected dichotomous relationship between in vitro CTL activity and in vivo tumor protection suggesting that an alternative mechanism of tumor destruction was invoked after co-administration of the CpG ODN with the vaccine.