The prognosis and response to conventional therapies of malignant melanoma inversely correlate with disease progression. With increasing thickness, melanomas acquire metastatic potential and become inherently resistant to radiotherapy and chemotherapy. These harsh realities mandate the design of improved therapeutic modalities, especially those targeting metastases. To develop an approach to effectively treat this aggressive disease, we constructed a conditionally replication-competent adenovirus in which expression of the adenoviral E1A gene, necessary for replication, is driven by the cancer-specific promoter of progression-elevated gene-3 (PEG-3) and which simultaneously expresses mda-7/IL-24 in the E3 region of the adenovirus (Ad.PEG-E1A-mda-7), a cancer terminator virus (CTV). This CTV produces large quantities of MDA-7/IL-24 protein as a function of adenovirus replication uniquely in cancer cells. Infection of Ad.PEG-E1A-mda-7 (CTV) in normal human immortal melanocytes and human melanoma cells demonstrates cancer cell-selective adenoviral replication, mda-7/IL-24 expression, growth inhibition and apoptosis induction. Injecting Ad.PEG-E1A-mda-7 CTV into xenografts derived from MeWo human metastatic melanoma cells in athymic nude mice completely eliminated not only primary treated tumors but also distant non-treated tumors (established in the opposite flank), thereby implementing a cure. These provocative findings advocate potential therapeutic applications of this novel virus for treating patients with advanced melanomas with metastases.