Therapeutic neoantigen cancer vaccines have limited clinical efficacy to date. Here, we identify a heterologous prime-boost vaccination strategy using a self-assembling peptide nanoparticle TLR-7/8 agonist (SNP) vaccine prime and a chimp adenovirus (ChAdOx1) vaccine boost that elicits potent CD8 T cells and tumor regression. ChAdOx1 administered intravenously (i.v.) had 4-fold higher antigen-specific CD8 T cell responses than mice boosted by the intramuscular (i.m.) route. In the therapeutic MC38 tumor model, i.v. heterologous prime-boost vaccination enhances regression compared with ChAdOx1 alone. Remarkably, i.v. boosting with a ChAdOx1 vector encoding an irrelevant antigen also mediates tumor regression, which is dependent on type I IFN signaling. Single-cell RNA sequencing of the tumor myeloid compartment shows that i.v. ChAdOx1 reduces the frequency of immunosuppressive Chil3 monocytes and activates cross-presenting type 1 conventional dendritic cells (cDC1s). The dual effect of i.v. ChAdOx1 vaccination enhancing CD8 T cells and modulating the TME represents a translatable paradigm for enhancing anti-tumor immunity in humans.