Conditionally replicating adenoviruses (CRADs) represent a promising new platform for the treatment of cancer. CRADs have been demonstrated to kill tumor cells when other therapies fail, indicating that their antitumor properties are complementary to, and distinct from, those of standard treatments such as chemotherapy and radiation. In clinic trials CRADs have shown encouraging results, demonstrating mild side effects when administered at high doses and via different routes, including intratumorally, intraperitoneally, and intravenously. Tumor-selective replication has been detected, although as a single agent the efficacy appears to be limited. Interestingly, combined treatment with radiation or chemotherapy has been found to enhance CRAD efficacy considerably. To date, the molecular mechanisms underlying adenovirus-mediated oncolysis, and the way in which chemotherapy enhances oncolysis, are not well understood. A fuller knowledge of these processes will open up new strategies to improve the cell-killing potential of CRADs. Here, we discuss several possibilities that may lead to CRADs with enhanced oncolytic activity. These approaches include strategies to functionally couple tumor targeting and optimal oncolytic activity, and ways to further increase tumor cell disruption at later stages of infection to facilitate the spreading of virus throughout the tumor mass. In addition, improved methods to evaluate the efficacy of these agents in animal models, and in the clinic, will be required to systematically test and optimize CRAD efficacy, also taking into account the influence of tumor characteristics and the administration route.