Intense efforts of research are made for developing antitumor vaccines that stimulate T cell-mediated immunity. Tumor cells specifically express at their surfaces antigenic peptides presented by MHC class I and recognized by CTL. Tumor antigenic peptides hold promise for the development of novel cancer immunotherapies. However, peptide-based vaccines face two major limitations: the weak immunogenicity of tumor Ags and their low metabolic stability in biological fluids. These two hurdles, for which separate solutions exist, must, however, be solved simultaneously for developing improved vaccines. Unfortunately, attempts made to combine increased immunogenicity and stability of tumor Ags have failed until now. Here we report the successful design of synthetic derivatives of the human tumor Ag Melan-A/MART-1 that combine for the first time both higher immunogenicity and high peptidase resistance. A series of 36 nonnatural peptide derivatives was rationally designed on the basis of knowledge of the mechanism of degradation of Melan-A peptides in human serum and synthesized. Eight of them were efficiently protected against proteolysis and retained the antigenic properties of the parental peptide. Three of the eight analogs were twice as potent as the parental peptide in stimulating in vitro Melan-specific CTL responses in PBMC from normal donors. We isolated these CTL by tetramer-guided cell sorting and expanded them in vitro. The resulting CTL efficiently lysed tumor cells expressing Melan-A Ag. These Melan-A/MART-1 Ag derivatives should be considered as a new generation of potential immunogens in the development of molecular anti-melanoma vaccines.