Metastatic cancer remains difficult to treat effectively and treatments are in most cases not curative despite significant side effects. Novel, targeted approaches such as gene therapy hold promise for the treatment of various tumor types. Among the most promising cancer gene therapy approaches are oncolytic adenoviruses, which are able to infect, replicate in and lyse tumor cells. Recent data from clinical trials with these vectors have shown that they are safe. However, antitumor efficacy needs to be improved to make oncolytic adenoviruses a viable treatment alternative for cancer patients. This review focuses on targeting strategies to improve tumor cell transduction and cancer cell selective replication. Strategies to improve antitumor efficacy by arming the virus with therapeutic transgenes are also discussed. Furthermore, an overview of the most important clinical approaches with oncolytic adenoviruses is given.