Inclusion Criteria:

- Stage IV metastatic melanoma of cutaneous or mucosal origin or without known primary
site

- At least one metastatic mass that is surgically resectable, excluding metastases
in brain, bowel, or bone

- Successful preparation of a vaccine that meets quality control release criteria

- Following surgery for vaccine preparation, subjects must have at least one
measurable metastasis defined by modified RECIST criteria. Non-measurable
metastases may also be present. Residual metastases (measurable or
non-measurable) must be limited to skin (dermal or subcutaneous), lymph node, or
lung, or a combination of these.

- No prior systemic treatment or one prior systemic treatment for metastatic
melanoma, not counting post-surgical adjuvant treatment with alpha interferon

- Minimum of one month and maximum of 4 months since the surgery

- Expected survival of at least 6 months

- Karnofsky performance status at least 80

- Signed informed consent

Exclusion Criteria:

- Failure to prepare a vaccine that meets all quality control release criteria

- Uveal melanoma

- Post-surgical residual metastases in sites other than specified in 6.1

- Brain metastases, current or past (unless successfully treated at least one year
prior to enrollment)

- Hepatic transaminase > 2.5 x ULN

- Total bilirubin > 2.0 mg/Dl

- Creatinine > 2.0 mg/Dl

- Hemoglobin < 10.0 g/Dl

- WBC < 3,000 /mm3

- Platelet count < 100,000/mm3

- Limited field radiotherapy, i.e., limited to recent surgical site, less than 4
weeks prior to first dose of vaccine

- Major field radiotherapy less than 6 months prior to first dose of vaccine

- Any systemic treatment for metastatic melanoma, including chemotherapy,
cytokines, or investigational drugs less than 2 months prior to first dose of
vaccine

- Previous administration of M-Vax

- Prior splenectomy

- Administration of systemic steroids less than 4 weeks prior to first dose of
vaccine. Topical steroids are allowed during the study, provided these are not
applied to vaccine injection sites. Inhaled aerosol steroids also are allowed
during the study.

- Administration of immunosuppressive drugs less than 4 weeks prior to first dose
of vaccine

- Administration of antitubercular drugs (e.g., isoniazid, rifampin, streptomycin)
less than 4 weeks prior to first dose of vaccine

- HIV 1/2 positive by ELISA, confirmed by Western blot

- Hepatitis B surface antigen or hepatitis C antibody positive

- Other malignancy within 5 years except: curatively treated non-invasive
melanoma, non-melanomatous skin cancer, carcinoma in situ of the uterine cervix,
or early stage (stage A or B1) prostate cancer

- Autoimmune diseases that would interfere with an immunologic response (e.g.,
systemic lupus erythematosus, multiple sclerosis or ankylosing spondylitis)

- Concurrent medical condition that would preclude compliance or immunologic
response to study treatment

- Concurrent serious infection, including active tuberculosis, or other serious
medical condition

- Pregnancy or lactation (serum human chorionic gonadotropin [HCG] test must be
negative in fertile women at screening visit)

- Known gentamicin allergy

- Anergic, defined by the inability to make a DTH to at least one of the
following: candida, mumps, tetanus or trichophyton (based upon availability)