Ideally, an oncolytic virus will replicate preferentially in malignant cells, have the ability to treat disseminated metastases, and ultimately be cleared by the patient. Here we present evidence that the attenuated vesicular stomatitis strains, AV1 and AV2, embody all of these traits. We uncover the mechanism by which these mutants are selectively attenuated in interferon-responsive cells while remaining highly lytic in 80% of human tumor cell lines tested. AV1 and AV2 were tested in a xenograft model of human ovarian cancer and in an immune competent mouse model of metastatic colon cancer. While highly attenuated for growth in normal mice, both AV1 and AV2 effected complete and durable cures in the majority of treated animals when delivered systemically.