The identification of CTL epitopes from tumor antigens is very important for the development of peptide-based, cancer-specific immunotherapy. Heparanase is broadly expressed in various advanced tumors and can serve as a universal tumor-associated antigen. Although several epitopes of heparanase antigen are known in humans, the corresponding knowledge in mice is still rather limited. The present study was designed to predict and identify the CTL epitopes in the mouse heparanase protein. For this purpose, H-2K(b)-restricted CTL epitopes were identified by using the following four-step procedure: (a) a computer-based epitope prediction from the amino acid sequence of mouse heparanase, (b) a peptide-binding assay to determine the affinity of the predicted epitopes with the H-2K(b) molecule, (c) the testing of the induction of CTLs toward various carcinoma cells expressing heparanase antigens and H-2K(b), and (d) the induction of immunoprotection and immunotherapy in vivo. The results showed that, of the tested peptides, effectors induced by peptides of mouse heparanase at residue positions 398 to 405 (LSLLFKKL; mHpa398) and 519 to 526 (FSYGFFVI; mHpa519) lysed three kinds of carcinoma cells expressing both heparanase and H-2K(b) (B16 melanoma cells, EL-4 lymphoma cells, and Lewis lung cancer cells). In vivo experiments indicated that mHpa398 and mHpa519 peptides offered the possibility of not only immunizing against tumors but also treating tumor-bearing hosts successfully. Our results suggest that the mHpa398 and mHpa519 peptides are novel H-2K(b)-restricted CTL epitopes capable of inducing heparanase-specific CTLs in vitro and in vivo. These epitopes may serve as valuable tools for the preclinical evaluation of vaccination strategies.