The polycomb group protein enhancer of zeste homolog 2 (EZH2) is linked to aggressive prostate cancer and could be an appropriate target in specific immunotherapy. In this study, we attempted to identify EZH2-derived peptides that have the potential to generate cancer-reactive cytotoxic T lymphocytes (CTLs) in human leukocyte antigen (HLA)-A2+ prostate cancer patients. Twelve EZH2-derived peptides were prepared based on the HLA-A2 binding motif. These peptide candidates were screened first by their ability to be recognized by immunoglobulin G (IgG), and then by their ability to induce peptide-specific cytotoxic T lymphocytes (CTLs). As a result, five EZH2 peptides recognized by IgG (EZH2 120-128, EZH2 165-174, EZH2 569-577, EZH2 665-674, and EZH2 699-708) were frequently detected in the plasma of prostate cancer patients. Among them, the EZH2 120-128 and EZH2 165-174 peptides effectively induced HLA-A2-restricted and cancer-reactive CTLs from prostate cancer patients. The cytotoxicity was mainly dependent on EZH2 peptide-specific and HLA-A2-restricted CD8+ T cells. These results indicate that these EZH2 120-128 and EZH2 165-174 peptides could be promising candidates in peptide-based immunotherapy for HLA-A2+ prostate cancer patients.