The immune system plays an important role in eliminating tumors. Accordingly, many immunotherapy protocols have been developed in attempts to boost anti-tumor immune responses in cancer patients. These trials most commonly aim at augmenting T-cell-, especially CD8+ T-cell, responses. In clinical trials performed to date, however, little correlation has been observed between parameters measured to assess cellular immune responses and clinical outcome. Thus, identification of reliable surrogate predictors for evaluation of cancer vaccine efficacy still remains to be accomplished and would be crucial for successfully pursuing clinically significant results. In this review, we discuss the role of different cellular components of the immune system in orchestrating and regulating an anti-tumor immune response, and how to reliably monitor these using polychromatic flow cytometry (FC). The increasing use of multi-parameter FC is expected to be as revolutionary for immunomonitoring as was the introduction of first generation technology. The application of this novel technology and more standardised monitoring assays should help identify biomarkers reliably distinguishing patients who respond to treatment.