Inclusion Criteria:

* Patients must have HLA-A2 status known prior to randomization; typing may be obtained through a local laboratory facility or through a reference lab utilized by the initiating institution; if typing is not available through these means, it may be obtained from the University of Pittsburgh
* All patients must have disease completely resected with one of the following in order to be eligible:

* Completely resected disease
* Any locoregional recurrence after prior adjuvant interferon or failure on S008
* Any local recurrence of disease after adequate surgical excision of the original primary
* Mucosal melanoma
* Stage IV melanoma (cutaneous, ocular, mucosal, or unknown primary)
* The following groups of patients may be entered onto this trial only if they are ineligible for S0008 or are, in the opinion of the managing physician, medically unfit to receive standard high-dose interferon:

* Any clinically evident satellite or in-transit disease
* Stage II disease with gross extracapsular extension
* Recurrence in a previously resected nodal basin
* Four or more involved lymph nodes or matted lymph nodes
* Ulcerated primary melanoma and any involved lymph nodes

* NOTE: Patients who are eligible for S0008 will be strongly encouraged to participate in that study in preference to this one
* Patients must have been surgically rendered free of disease with negative margins on resected specimens; patients rendered free of disease by non-surgical means are not eligible
* Patients must be randomized within 112 days (16 weeks) of surgical resection; if more than one surgical procedure is required to render the patient disease-free, all required surgeries must be accomplished within this 16 week time period
* Patients must not have received any adjuvant treatment (chemotherapy, biotherapy, or limb perfusion) after the resection(s) that make(s) them eligible for this trial; one systemic treatment after a prior surgery is allowed, and must have been completed >= 8 weeks prior to randomization; (when chemotherapy and biotherapy are given together as one planned treatment \[biochemotherapy\], this counts as one regimen); NOTE: Previous radiation therapy, including after the resection, is allowed as long as 30 days elapse between the radiation and initiation of therapy
* Prior treatment with GM-CSF or any peptides used in this protocol, is not allowed
* Patients must have Eastern Cooperative Oncology Group (ECOG) performance status of 0-1
* Patients must not have an active infection requiring treatment with parenteral antibiotics
* Patients must not have other significant medical, surgical, or psychiatric conditions or require any medication or treatment that may interfere with compliance on any of the E4697 treatment regimens
* Patients must not have a diagnosis or evidence of organic brain syndrome or significant impairment of basal cognitive function or any psychiatric disorder that might preclude participation in the full protocol
* Patients must be able to self-administer or arrange for administration of subcutaneous injections
* Patients who have other current malignancies are not eligible
* Patients with prior history at any time of any in situ cancer, lobular carcinoma of the breast in situ, cervical cancer in situ, atypical melanocytic hyperplasia or Clark I melanoma in situ are eligible; patients who meet this criteria must be disease-free at time of randomization
* Patients with prior history of basal or squamous skin cancer are eligible; patients who meet this criteria must be disease-free at time of randomization
* Patients who have had multiple primary melanomas are eligible
* Patients with other malignancies are eligible if they have been continuously disease free for > 5 years prior to the time of randomization
* Patients must not have autoimmune disorders, conditions of immunosuppression or treatment with systemic corticosteroids, including oral steroids (i.e., prednisone, dexamethasone), continuous use of topical steroid creams or ointments, or any steroid containing inhalers; replacement doses of steroids for patients with adrenal insufficiency are allowed; patients who discontinue use of these classes of medication for at least 2 weeks prior to randomization are eligible if, in the judgment of the treating physician, the patient is not likely to require these classes of drugs during the study
* Women of childbearing potential must not be pregnant (negative beta human chorionic gonadotropin \[bHCG\] within 2 weeks prior to randomization) or breast-feeding
* Women of childbearing potential and sexually active males must be counseled to use an accepted and effective method of contraception (including abstinence) while on treatment and for a period of 18 months after completing or discontinuing treatment
* All patients must have brain computed tomography (CT) or magnetic resonance imaging (MRI), chest CT or chest x-ray (CXR), and abdominal (liver) CT or MRI within 4 weeks prior to randomization; positron emission tomography (PET) scans are also acceptable in place of CT, CXR and/or abdominal MRI if obtained within 4 weeks prior to randomization; patients with lesions on the lower extremity must also have pelvic imaging within this time period; this is also strongly recommended for patients with lesions on the lower trunk; PET scans are acceptable
* Patients with resection of visceral disease must have imaging of the affected area/organ documenting disease-free status within 2 weeks prior to randomization
* White blood cells (WBC) >= 3,000/mm?
* Platelet count >= 100,000/mm?
* Serum glutamic oxaloacetic transaminase (SGOT) (aspartate aminotransferase \[AST\]) =< 2 x institutional upper limit (IUL) of normal
* Bilirubin =< 2 x IUL of normal
* Serum creatinine =< 1.8 mg/dl
* Alkaline phosphatase and lactate dehydrogenase (LDH) must be performed within 4 weeks prior to randomization; LDH must be normal; patients with abnormal alkaline phosphatase which is =< 1.25 times the institutional upper limit of normal who have a negative CT or MRI of the liver and negative bone scan or a negative PET scan are eligible
* Patients with bone pain must have a bone scan within 4 weeks prior to randomization to document the absence of tumor