Progress in vector design and an increased knowledge of mechanisms underlying tumor-induced immune suppression have led to a new and promising generation of Adenovirus (Ad)-based immunotherapies, which are discussed in this review. As vaccine vehicles Ad vectors (AdVs) have been clinically evaluated and proven safe, but a major limitation of the commonly used Ad5 serotype is neutralization by preexistent or rapidly induced immune responses. Genetic modifications in the Ad capsid can reduce intrinsic immunogenicity and facilitate escape from antibody-mediated neutralization. Further modification of the Ad hexon and fiber allows for liver and scavenger detargeting and selective targeting of, for example, dendritic cells. These next-generation Ad vaccines with enhanced efficacy are now becoming available for testing as tumor vaccines. In addition, AdVs encoding immune-modulating products may be used to convert the tumor microenvironment from immune-suppressive and proinvasive to proinflammatory, thus facilitating cell-mediated effector functions that can keep tumor growth and invasion in check. Oncolytic AdVs, that selectively replicate in tumor cells and induce an immunogenic form of cell death, can also be armed with immune-activating transgenes to amplify primed antitumor immune responses. These novel immunotherapy strategies, employing highly efficacious AdVs in optimized configurations, show great promise and warrant clinical exploration.