Vaccinia virus (VACV)-derived vectors are popular candidates for vaccination against diseases such as HIV-1, malaria and tuberculosis. However, their genomes encode a multitude of proteins with immunomodulatory functions, several of which reduce the immunogenicity of these vectors. Hitherto only limited studies have investigated whether the removal of these immunomodulatory genes in combination can increase vaccine efficacy further. To this end we constructed viruses based on VACV strain Western Reserve (WR) lacking up to three intracellular innate immunomodulators (N1, C6 and K7). These genes were selected because the encoded proteins had known functions in innate immunity and the deletion of each gene individually had caused a decrease in virus virulence in the murine intranasal and intradermal models of infection and an increase in immunogenicity. Data presented here demonstrate that deletion of two, or three of these genes in combination attenuated the virus further in an incremental manner. However, when vaccinated mice were challenged with VACV WR the double and triple gene deletion viruses provided weaker protection against challenge. This was accompanied by inferior memory CD8(+) T cell responses and lower neutralising antibody titres. This study indicates that, at least for the three genes studied in the context of VACV WR, the single gene deletion viruses are the best vaccine vectors, and that increased attenuation induced by deletion of additional genes decreased immunogenicity. These data highlight the fine balance and complex relationship between viral attenuation and immunogenicity. Given that the proteins encoded by the genes examined in this study are known to affect specific aspects of innate immunity, the set of viruses constructed here are interesting tools to probe the role of the innate immune response in influencing immune memory and vaccine efficacy.