Recombinant vaccinia viruses have shown promise as vaccine vectors. However, their effectiveness is markedly reduced by pre-existing anti-vaccinia immunity. The possibility of new vaccinia immunizations in the event of a bioterror-related smallpox release poses an additional negative impact on the utility of vaccinia-based vectors. Thus, we aimed to design a vaccinia vector that would enhance the immune response to an expressed foreign protein in a pre-immune animal model. To do this, we made use of the finding that most neutralizing antibodies against the extracellular form of vaccinia virus are directed against the B5 protein. We found that mice immunized with vaccinia, primed with Gag plasmid DNA, and boosted with a recombinant vaccinia virus lacking the majority of the B5 ectodomain expressing a test antigen, HIV Gag, had stronger anti-Gag immune responses than mice that were boosted with a wild-type virus-expressing Gag. These findings are particularly striking given the more attenuated phenotype of this virus, as compared to its wild-type counterpart. Importantly, we found that vaccination with a B5R deletion virus, followed by boosting with the Gag-expressing virus lacking the majority of the B5 ectodomain, resulted in poorer anti-Gag immune responses. Thus, recombinant vaccinia viruses lacking the B5 ectodomain may serve as vaccine vectors in DNA prime-vaccinia boost vaccinations of individuals with pre-existing immunity against vaccinia. These data open the possibility of extending the potential benefit of replication competent recombinant vaccinia virus vectors to a larger population.