Limitations of current viral-based gene therapies for malignant tumors include lack of cancer-specific targeting and insufficient tumor delivery. To ameliorate these problems and develop a truly effective adenovirus gene-based therapy for cancer, we constructed a conditionally replication competent adenovirus (CRCA) manifesting the unique properties of tumor-specific virus replication in combination with production of a cancer-selective cytotoxic cytokine, melanoma differentiation associated gene-7/interleukin-24 (mda-7/IL-24), which embodies potent bystander antitumor activity. Cancer cell selective tropism was ensured by engineering the expression of the adenoviral E1A protein, necessary for viral replication, under the control of a minimal promoter region of progression elevated gene-3 (PEG-3), which functions selectively in diverse cancer cells with minimal activity in normal cells. In the E3 region of this CRCA, we introduced the mda-7/IL-24 gene, thereby mediating robust production of this cytokine as a function of adenovirus replication. Infection of this CRCA (designated Ad.PEG-E1A-mda-7) in normal mammary epithelial cells and breast cancer cells confirmed cancer cell selective adenoviral replication, mda-7/IL-24 expression, growth inhibition, and apoptosis induction. Injecting Ad.PEG-E1A-mda-7 into human breast cancer xenografts in athymic nude mice completely eradicated not only the primary tumor but also distant tumors (established on the opposite flank of the animal) thereby implementing a cure. This dual cancer-specific targeting strategy provides an effective approach for treating breast and other human neoplasms with the potential for eradicating both primary tumors and metastatic disease. Additionally, these studies support the potential use of mda-7/IL-24 in the therapy of malignant cancers.