Heterologous “prime-boost” regimens that involve priming with plasmid DNA vaccines and boosting with recombinant viral vectors have been shown to elicit potent virus-specific cytotoxic T-lymphocyte responses. Increasing evidence, however, suggests that the utility of recombinant viral vectors in human populations will be significantly limited by preexisting antivector immunity. Here we demonstrate that the coadministration of plasmid chemokines and colony-stimulating factors with plasmid DNA vaccines markedly increases the immunogenicity of DNA prime-recombinant adenovirus serotype 5 (rAd5) boost and DNA prime-recombinant vaccinia virus (rVac) boost vaccine regimens in BALB/c mice. In mice with preexisting anti-Ad5 immunity, priming with the DNA vaccine alone followed by rAd5 boosting elicited only marginal immune responses. In contrast, cytokine-augmented DNA vaccine priming followed by rAd5 vector boosting was able to generate potent immune responses in mice with preexisting anti-Ad5 immunity. These data demonstrate that plasmid cytokines can markedly improve the immunogenicity of DNA prime-viral vector boost vaccine strategies and can partially compensate for antivector immunity.