Patients with relapsed acute myeloid leukemia (AML) have limited therapeutic options. Vesicular stomatitis virus (VSV)–interferon β (IFNβ)–sodium iodide symporter (NIS) is an oncolytic VSV encoding IFNβ and the NIS reporter. Syngeneic AML C1498 tumors responded to IV therapy with VSV-murine IFNβ (mIFNβ)-NIS in a dose-dependent manner. Imaging for NIS expression showed robust virus infection within the tumors. Virus infection did not increase programmed death ligand 1 (PD-L1) on tumor cells. Combining VSV-mIFNβ-NIS with anti-PD-L1 antibody (Ab) therapy enhanced antitumor activity compared with treatment with virus alone or Ab alone; this enhancement was not significant at higher VSV-mIFNβ-NIS doses. Systemic VSV therapy reduced systemic C1498–green fluorescent protein (GFP) tumor burden in the blood, bone marrow, spleen, and liver of mice with AML. Combination VSV-mIFNβ-NIS and anti-PD-L1 Ab therapy significantly enhanced the survival of these mice with no evidence of toxicity, compared with isotype control, anti-PD-L1, or virus alone. There was an increase in tumor-infiltrating CD4 and CD8 cells. Single-agent VSV-mIFNβ-NIS virotherapy induced both VSV-specific and GFP-specific CD8 T cells as determined by IFN-γ enzyme-linked immunospot, pentamer, and intracellular IFN-γ staining assays. Both of these responses were further enhanced by addition of anti-PD-L1 Ab. Depletion of CD8 or natural killer cells, but not CD4 cells, resulted in loss of antitumor activity in the VSV/anti-PD-L1 group. Clinical samples from chronic myelomonocytic leukemia and acute myelomonocytic leukemia appear to be especially susceptible to VSV. Overall, our studies show that oncolytic virotherapy combined with immune checkpoint blockade is a promising approach to AML therapy.