Inclusion Criteria:

Same for Phase I & II

• Cytologically/histologically-documented metastatic (stage IV) malignant melanoma
• Age greater than or equal to 18 years old
• ECOG performance status 0-2
• Subjects must be able to give informed consent and be able to follow the guidelines given in the study
• The subject has no major impairment of hematological function, as defined by the following laboratory parameters: WBC > 3.0x109/L; ANC > 1.5 x 109/L; Hgb > 9.0g/dL; PLT >100x109/L. Red blood cell transfusions and repeat evaluations for study entry are allowed
• All subjects of reproductive potential must use an effective method of contraception during the study and three months following termination of treatment (Not applicable to patients with bilateral oophorectomy and/or hysterectomy or to those patients who are postmenopausal.)
• Subjects with biopsiable disease are preferred but not mandatory; subjects with biopsiable disease will be encouraged to undergo biopsy.

Exclusion Criteria:

Phase I:

• Subjects must not have evidence of significant active infection (e.g., pneumonia, cellulitis, wound abscess, etc.) at time of study entry.
• Subjects must have adequate renal and normal hepatic function (creatinine < 1.5 x upper limit of normal (ULN), bilirubin and SGOT (AST) < 1.5 X ULN) obtained within 4 weeks prior to registration.
• Pregnant women are excluded from the study because VPA is known to cause birth defects. Nursing mothers are excluded from this trial as effects on newborns and excretion of either drug in milk is unknown.
• Women of childbearing age must have a negative pregnancy test and be willing to use a highly effective method of contraception. Men who are sexually active must also be willing to use an accepted and effective method of contraception.
• Subjects with uncontrolled CNS metastasis or a history of seizures are excluded. Subjects with stable CNS metastasis (either surgically resected, treated with the gamma knife or stable for 3 months following whole brain radiotherapy are eligible)

Phase II:

• Subjects must not have evidence of significant active infection (e.g., pneumonia, cellulitis, wound abscess, etc.) at time of study entry.
• Subjects must have adequate renal and normal hepatic function (creatinine < 1.5 x upper limit of normal (ULN), bilirubin and SGOT (AST) < 1.5 X ULN) obtained within 4 weeks prior to registration.
• Pregnant women are excluded from the study because VPA is known to cause birth defects. Nursing mothers are excluded from this trial as effects on newborns and excretion of either drug in milk is unknown.
• Women of childbearing age must have a negative pregnancy test and be willing to use a highly effective method of contraception. Men who are sexually active must also be willing to use an accepted and effective method of contraception.
• Subjects with uncontrolled CNS metastasis or a history of seizures are excluded. Subjects with stable CNS metastasis (either surgically resected, treated with the gamma knife or stable for 3 months following whole brain radiotherapy are eligible)
• Subjects who have been previously treated with more than 2 prior chemotherapy regimens. Any previous immunotherapy regimens are allowed.