CD8+ cytotoxic T lymphocytes (CTLs) play an important role in antitumor immunity. Induction of tumor-specific CTLs is one major strategy for tumor immunotherapy. However, therapeutic vaccinations used to treat firmly established tumors are generally ineffective. A thorough understanding of the mechanisms underlying tumor resistance to CTL-based therapeutic vaccination is very important in the tumor immunology field. There are two main mechanisms by which tumors develop resistance to CTL-based therapeutic vaccinations. One is that tumors induce peripheral tolerance of tumor-specific CD8+ T cells. The other is that tumor cells themselves develop immune evasion mechanisms to prevent recognition and killing by CTLs. This review focuses on recently reported cellular and molecular mechanisms of CD8+ T cell tolerance and immune evasion in tumors and discusses about the possibilities to improve tumor immunotherapy.