Background: The use of oncolytic adenoviruses as cancer gene therapy is limited by their uneven penetration and distribution in tumors. We investigated whether the expression of the cell matrix–degradative protein relaxin by adenovirus could improve adenovirus distribution and penetration in tumors. Methods: We generated relaxin-expressing, replication-incompetent (dl-lacZ-RLX) and -competent (Ad-ΔE1B-RLX) adenoviruses by inserting a relaxin gene into the E3 adenoviral region. Controls were parental adenoviruses (dl-lacZ and Ad-ΔE1B) and phosphate-buffered saline (PBS) (vehicle). Replication-incompetent viruses, which do not lyse cells, were used to assess transduction efficiency. Viral spread in tumor spheroids, made by dissecting tumor tissue into homogeneous fragments, was assessed by reporter gene (i.e., lacZ) expression. Tumor growth inhibition was assessed by injecting adenoviruses into xenograft tumors in athymic mice (n = 8 or 9). Overall survival was assessed by the Kaplan–Meier method. Extracellular matrix was examined with Masson's trichrome staining. Therapeutic efficacy was evaluated by assessing spontaneous pulmonary metastasis in the B16BL6 melanoma mouse model and growth inhibition of orthotopically implanted hepatoma (n = 4–6). All statistical tests were two-sided. Results: In tumor spheroids and established solid tumors in vivo, transduction with dl-lacZ-RLX, compared with parental virus or vehicle, elicited higher transduction efficiency and viral spread throughout the tumor mass. Infection with Ad-ΔE1B-RLX, compared with parental virus, elicited greater viral persistence and spread, leading to increased survival (e.g., 100%, 95% confidence interval CI = 63.1% to 100%, for C33A tumor-bearing mice treated with Ad-ΔE1B-RLX, and 50%, 95% CI = 15.7% to 84.3%, for C33A tumor-bearing mice treated with Ad-ΔE1B). Infection with Ad-ΔE1B-RLX substantially decreased the collagen content of tumor tissue but not of adjacent normal tissue, compared with noninfected tissues. Intratumoral injection of Ad-ΔE1B-RLX inhibited the formation of lung metastases in mice (PBS = 268 mg of metastatic tumor per mouse and Ad-ΔE1B-RLX = 10 mg; difference = 258 mg, 95% CI = 94 to 426; P = .003, Mann–Whitney test). Systemic treatment with Ad-ΔE1B-RLX completely inhibited the growth of Hep1 hepatocellular carcinomas (PBS = 20.2 mg of tumor per mouse and Ad-ΔE1B-RLX = 0 mg; difference = 20.2 mg, 95% CI = 3.7 to 36.7; P = .004, Mann–Whitney test). Conclusion: Extracellular matrix degradation by relaxin expressed by adenoviruses increased viral distribution and tumor penetration, inhibited tumor growth and metastasis, and increased survival of mice.