Increased expression and secretion of heparanase (Hpa) by tumor cells promotes tumor invasion through extracellular matrices, tissue destruction, angiogenesis, and metastasis. Here, we show the existence in breast cancer patients of Hpa-specific T lymphocytes by fluorescence-activated cell sorting flow cytometry using Hpa peptide-MHC class I tetramers. We furthermore show memory T-cell responses in a high proportion of breast cancer patients to Hpa-derived HLA-A2-restricted peptides, leading to production of IFN-γ and to generation of antitumor CTLs lysing breast cancer cells. Such CTLs recognized endogenously processed respective Hpa peptides on Hpa-transfected and Hpa-expressing untransfected breast carcinoma cells. According to these results and to the fact that such cells were not found in healthy people, Hpa seems to be an attractive new tumor-associated antigen and its HLA-A2-restricted peptides ought to be good candidates for peptide vaccination to reactivate memory immune responses to invasive and metastatic cancer cells. (Cancer Res 2006; 66(15): 7716-23)