Viral vectors have been developed as vaccine platforms for a number of pathogens and tumors. In particular, adenovirus (Ad)-based vectors expressing genes coding for pathogen or tumor antigens have proven efficacious to induce protective immunity. Major challenges in the use of Ad vectors are the high prevalence of anti-Ad immunity and the recent observation during an Ad-based HIV vaccine trial that led to increased HIV-1 acquisition in the presence of circulating anti-Ad5 neutralizing antibodies. In this review we summarize strategies to address these challenges and focus on modifications of the Ad capsid to enhance the adjuvant effect of anti-Ad immunogenicity and to circumvent pre-existing immunity. In addition, we summarize the current status and potential of other viral vector vaccines based on adeno-associated viruses, lentiviruses and poxviruses.