Adenoviruses (Ad) are commonly used both experimentally and clinically, including oncolytic virotherapy applications. In the clinical area, efficacy is frequently hampered by the high rates of neutralizing immunity, estimated as high as 90% in some populations that promote vector clearance and limit bioavailability for tumor targeting following systemic delivery. Active tumor targeting is also hampered by the ubiquitous nature of the Ad5 receptor, hCAR, as well as the lack of highly tumor-selective targeting ligands and suitable targeting strategies. Furthermore, significant off-target interactions between the viral vector and cellular and proteinaceous components of the bloodstream have been documented that promote uptake into non-target cells and determine dose-limiting toxicities. Novel strategies are therefore needed to overcome the obstacles that prevent efficacious Ad deployment for wider clinical applications. The use of less seroprevalent Ad serotypes, non-human serotypes, capsid pseudotyping, chemical shielding and genetic masking by heterologous peptide incorporation are all potential strategies to achieve efficient vector escape from humoral immune recognition. Conversely, selective vector arming with immunostimulatory agents can be utilized to enhance their oncolytic potential by activation of cancer-specific immune responses against the malignant tissues. This review presents recent advantages and pitfalls occurring in the field of adenoviral oncolytic therapies.