Up to 24 patients with stage III or stage IV melanoma will be enrolled. Patients who are currently disease-free but at high risk for relapse are also eligible. Patients will receive vaccinations of gp75 at assigned dose levels. Patients who exhibit serologic and stable/clinical response are eligible to receive booster vaccinations. Patients will be evaluated for safety and efficacy throughout the duration of the study. In this study, the optimal biologically effective dose is defined as the lowest dose of gp75 that results in the production of anti-gp75 antibodies.

This study is designed to evaluate the safety and feasibility of intramuscular vaccination with gp75 DNA in patients with stage III or IV melanoma. Secondary objectives are to observe the patient for any evidence of anti-tumor response and to establish the optimal biologically effective dose. Up to 24 evaluable patients with stage III or IV metastatic melanoma or with stage III melanoma, currently disease-free, but at high risk for recurrence will be enrolled. Patients will be be enrolled into an assigned dose group and will receive five vaccinations of gp75. In order for dose escalation to proceed, only one patient in the current dose group may have demonstrated a dose limiting toxicity (DLT). If a second patient experiences such toxicity then both patients will move down to the previous dose level, and the previous dose level will be considered to be the MTD. If no DLTs are encountered, patients will continue on study at the assigned dose level. Any patient experiencing a DLT will not receive further vaccination until the toxicity has resolved. Patients exhibiting both serological and stable/clinical response after receiving the fifth vaccination will be eligible to receive booster vaccinations. An additional patient will be accrued to the dose level for every patient that progresses prior to the fifth vaccination.

Inclusion Criteria:

1. The patient has a diagnosis of American Joint Commission on Cancer (AJCC) stage 111 or IV malignant melanoma. A patient who is free of disease after surgical resection of stage 111 or IV disease, but at high risk (defined as a primary tumor >4 rnm, satellite or in-transit lesions, one or more positive lymph nodes or distant metastases) for recurrence is also eligible. A patient with metastatic disease may have no more than five sites of disease. The skin represents one site regardless of the number of lesions. Stage 111 melanoma is defined as a pT4 primary tumor (>4m in depth or Clark level 5) in-transit metastases, satellites lesions or regional lymph nodes involved with melanoma.Pathology slides must be reviewed by the investigational site's Department of Pathology.
2. The patient's Karnofsky performance status is 280 at study entry.
3. The patient has given signed informed consent.
4. The patient has had surgery for their melanoma at least 6 months prior to study entry, or has had prior interferon therapy, or developed unacceptable toxicities to interferon therapy, or has a pre-existing condition(s) that precludes the patient fkom receiving interferon treatment.
5. The patient is 21 8 years of age.
6. The patient must have completed any prior irradiation, chemotherapy, or systemic immunotherapy (interferon-alpha, or interleukin-2) at least 30 days prior to study entry.
7. The patient has adequate hematologic function as defined as a platelet count 2100,000/mm3 and white blood cell (WBC) level 23,000/mm3.
8. The patient has serum lactose dehydrogenase (LDH) within normal range and a serum creatinine level <2.0 mg/dL.
9. The patient agrees to use effective contraception if procreative potential exists.

Exclusion Criteria:

1. The patient has stage I11 disease otherwise eligible to receive standard of care melanoma therapy.
2. The patient has a medical condition or use of medication (eg, corticosteroids) that might make it difficult for the patient to complete the full course of treatments or to respond immunologically to them, in the opinion of the investigator.
3. The patient has received irradiation, chemotherapy, or systemic immunotherapy (interferon-alpha, or interleukin-2) within 30 days prior to study entry.
4. The patient is pregnant (confirmed by serum beta human chorionic gonadotropin [PHCG], if applicable) or is breast feeding.
5. The patient has received any investigational agents within 30 days of study entry.
6. The patient has received prior cancer vaccine therapy.
7. The patient has evidence of central nervous system (CNS) metastasis.
8. The patient has evidence of an ocular abnormality, as detected by a slit-lamp ophthalmologic examination, within 4 weeks prior to study entry.