The efficacy of cancer vaccines has been limited by the immunosuppressive tumor microenvironment, which can be alleviated by immune checkpoint inhibitor (ICI) therapy. Here, we tested if oncolytic viruses (OVs), similar to ICI, can also synergize with cancer vaccines by modulating the tumor microenvironment. VSV-GP, a chimeric vesicular stomatitis virus (VSV) pseudotyped with the glycoprotein (GP) of the lymphocytic choriomeningitis virus, is a promising new OV candidate. Here, we show that in mouse B16-OVA melanoma, combination treatment of VSV-GP with an ovalbumin (OVA) peptide-loaded dendritic cell (DC) vaccine (DCVacc) significantly enhanced survival over the single agent therapies, although both DCVacc and DCVacc/VSV-GP treatments induced comparable levels of OVA-specific CD8 T cell responses. Virus replication was minimal so that direct viral oncolysis in B16-OVA did not contribute to this synergism. The strong therapeutic effect of the DCVacc/VSV-GP combination treatment was associated with high numbers of tumor-infiltrating, highly activated T cells and the relative reduction of regulatory T cells in treated and contra-lateral nontreated tumors. Accordingly, depletion of CD8 T cells but not natural killer cells abrogated the therapeutic effect of DCVacc/VSV-GP supporting the crucial role of CD8 T cells. In addition, a drastic increase in several proinflammatory cytokines was observed in VSV-GP-treated tumors. Taken together, OVs, similar to ICI, have the potential to markedly increase the efficacy of cancer vaccines by alleviating local immune suppression in the tumor microenvironment.