It is somewhat of a paradox that a tumor may be immunogenic in the host, yet grow and disseminate with impunity. To account for this, it has been suggested that tumors escape from immune regulation due to dynamic changes in antigen expression, and deficiencies in antigen processing or co-stimulatory factors. Interestingly, therapeutic vaccinations at early stages often prove effective in inducing anti-tumor immunity and retarding or preventing tumor growth. Cytokines elaborated during tumor progression or subsequent to vaccination have diverse effects favoring either the tumor or the host. Cytotoxic CD8⁺ T lymphocytes (CTLs) are pivotal in anti-tumor immunity. Since cytokines can modify their activity, numerous studies have focused on changes in cytokine profile during active tumor growth or after a therapeutic manipulation. Recent reports suggest that there is complexity in cytokine-mediated interaction between tumors and T-cells, as different subsets of helper T cells (Th) and CTLs respond differently to various cytokines. These cytokines may come from T-cells, neighboring host cells or tumor cells. Our studies on murine lymphoma indicate that CTLs at the late stage but not those occurring early during tumor progression exhibit little cytolytic activity and are strikingly deficient in both IL-4 and IFN-γ. However, only IL-4 can effectively restore the activity of these late CTLs. Interestingly, CTLs from hyperimmune tumor-free mice secrete moderate levels of IL-4 and IFN-γ. In this review, we discuss these and other findings from different laboratories and suggest that anti-tumor immunity depends not only on tumor antigen and co-stimulator molecules but also the cytokine milieu of the tumor-bearing host (TBA).