Cytotoxic T cells are considered crucial for antitumor immunity and their induction is the aim of various immunotherapeutic strategies. High frequencies of tumor-specific CD8+ T cells alone, however, are no guarantee for long-term tumor control. Here, we analyzed the functionality of tumor-specific CD8+ T cells in melanoma patients upon dendritic cell vaccination by measuring multiple T cell effector functions considered crucial for anticancer immunity, including the expression of pro-inflammatory cytokines, chemokines and cytotoxic markers (IFNγ, TNFα, IL-2, CCL4, CD107a). We identified small numbers of multifunctional (polyfunctional) tumor-specific CD8+ T cells in several patients and dendritic cell therapy was able to improve the functionality of these pre-existing tumor-specific CD8+ T cells. Generated multifunctional CD8+ T cell responses could persist for up to ten years and within the same patient functionality could vary greatly for the different vaccination antigens. Importantly, after one cycle of DC vaccination highly functional CD8+ T cells were only detected in patients displaying prolonged overall survival. Our results shed light on the dynamics of multifunctional tumor-specific CD8+ T cells during metastatic melanoma and reveal a new feature of dendritic cell vaccination in vivo.