The majority of shared melanoma antigens identified thus far can be divided into two groups; 1) melanocyte differentiation proteins (MDP) and 2) cancer-testis antigens (CTA). Generally, both types of proteins are encoded by non-mutated genes, which lack tumor-specific mutations. Therefore, epitopes derived from these molecules could be useful in a vaccine for a large population of melanoma patients. Interestingly, MDP and CTA are differentially expressed in various stages of melanoma. Generally, the expression of MDA decreases in more metastatic lesions, whereas the expression of CTA increases in metastatic lesions. Thus, metastatic tumors contain a heterogeneous population of cells with respect to protein expression, Based on the emergence of metastases that have lost expression of target antigens vaccines that incorporate single melanoma derived epitopes may be inadequate in generating a complete immune response against the tumor. Ideally, a polyvalent vaccine that incorporates epitopes derived from both groups of antigens should compensate for the differential display of melanoma-associated antigens. Preliminary data from an ongoing vaccine trial at the University of Virginia (UVA-Me139) support the safety and immunogenicity of a vaccine strategy incorporating 12 melanoma peptides. This 12-peptide preparation will be used in the currently proposed study. Granulocyte-macrophage colony stimulating factor (GM-CSF) has been included in our vaccine regimens as a local cytokine adjuvant. The rationale for inclusion of GM-CSF is based on substantial murine and human data, but other studies with Montanide ISA-51 adjuvant alone have been demonstrated immunogenicity in the absence of GMCSF. In the present study, we propose to test the hypothesis that the GM-CSF included in this regimen contributes to a heightened cellular immune response compared to vaccination in Montanide ISA-51 adjuvant alone. A second question being addressed in this study is the immunologic consequences of vaccination in more than one injection site. In the following study, we propose a 2-by-2 design to address both questions. The primary goals are to estimate: (1) whether GM-CSF administered locally changes the immunogenicity of vaccination with multiple synthetic melanoma peptides in an emulsion with incomplete Freund's adjuvant, (2) whether vaccination at two extremity sites induces different immunogneicty than vaccination at a single site. Secondary goals are to obtain preliminary data on (3) whether booster vaccination every three months may maintain immune responses to a peptide vaccine, and (4) whether celluar immune responses to a 12-peptide vaccine may correlate with clinical outcome.