OUTLINE: This is a randomized, parallel study. Patients are stratified by prior therapy (immunotherapy or chemotherapy vs surgery only). Patients are randomized to receive 1 of 2 treatment arms: Arm I: Following surgery, patients receive tyrosinase and gp100 peptides emulsified with Montanide ISA-51 (ISA-51) subcutaneously (SQ) once weekly during weeks 0, 2, 4, 6, 10, 14, 18, and 26 for a total of 8 vaccinations. Arm II: Following surgery, patients receive treatment as in Arm I followed by interleukin-12 SQ once weekly during weeks 0, 2, 4, 6, 10, 14, 18, and 26 for a total of 8 vaccinations. Patients are followed at 2-4 weeks, then every 3 months for 2 years after resection, then every 6 months for 3 years, and then yearly if without evidence of disease.