Inclusion Criteria:
* Histologically-confirmed, Stage 3 or Stage 4 malignant melanoma
* At least one tumor mass measurable by CT/MRI and/or physical examination that can be injected by direct visualization or by ultrasound-guidance
* Anticipated survival of at least 16 weeks
* Cancer is not surgically resectable for cure
* KPS score of ≥ 70 (refer to APPENDIX E: KARNOFSKY PERFORMANCE STATUS (KPS))
* Age ≥18 years
* Men and women of reproductive potential must be willing to follow accepted birth control methods during treatment and for 3 months after the last treatment with JX-594
* The ability to understand and willingness to sign an Institutional Review Board (IRB)/Independent Ethics Committee (IEC)-approved written informed consent form
* Able to comply with study procedures and follow-up examinations
* Adequate liver function: Total bilirubin ≤ 2.0 x ULN; AST, ALT ≤ 2.0 x ULN
* Adequate bone marrow function: WBC \> 3,500 cells/mm3 and \< 50,000 cells/mm3; ANC \> 1,500 cells/mm3; Hemoglobin \> 10 g/dL; Platelet count \> 125,000 plts/mm3
* Acceptable coagulation status: INR \< (ULN + 10%)
* Acceptable kidney function: Serum creatinine \< 2.0 mg/dL
Exclusion Criteria:
* Target tumor(s) adherent to and/or invading a major vascular structure (e.g. carotid artery)
* Pregnant or nursing an infant
* Known infection with HIV
* Systemic corticosteroid or other immunosuppressive medication use within 4 weeks of first treatment with JX-594
* Clinically significant active infection or uncontrolled medical condition (e.g. pulmonary, neurological, cardiovascular, gastrointestinal, genitourinary) considered high risk for investigational new drug treatment Significant immunodeficiency due to underlying illness and/or medication (e.g. systemic corticosteroids)
* History of eczema that at some stage has required systemic therapy
* Clinically significant and/or rapidly accumulating ascites, peri-cardial and/or pleural effusions (e.g. requiring drainage for symptom control)
* Severe or unstable cardiac disease which includes, but is not limited to, any of the following within 6 months prior to screening: myocardial infarct, unstable angina, congestive heart failure, myocarditis, arrhythmias diagnosed and requiring medication, or any clinically-significant change in cardiac status
* Treatment of the target tumor(s) with radiotherapy, chemotherapy, surgery, or an investigational drug within 4 weeks of screening (6 weeks in case of mitomycin C or nitrosoureas)
* Experienced a severe reaction or side-effect as a result of a previous smallpox vaccination
* Inability or unwillingness to give informed consent or comply with the procedures required in this protocol
* Patients with household contacts who are pregnant or nursing an infant, children \< 5 years old, have history of eczema that at some stage has required systemic therapy, or have a significant immunodeficiency due to underlying illness (e.g. HIV) and/or medication (e.g. systemic corticosteroids) will be excluded unless alternate living arrangements can be made during the patient's active dosing period and for three weeks following the last dose of study medication.
