Oncolytic viruses are a class of novel therapeutic agents used for the treatment of cancer that have the unique property of tumor-dependent self-perpetuation. Initial clinical trials have demonstrated that these agents are very safe and well tolerated. However, to date they have failed to demonstrate therapeutic benefit as monotherapies and as a consequence, next-generation oncolytic adenoviruses are now needed. This review discusses the approaches to deriving next-generation oncolytic adenoviruses together with potential preclinical test systems that might better predict their clinical outcome. Many of these approaches and test systems may be applicable to other viral systems being developed as oncolytic agents.