The tumor microenvironment (TME) influences cancer progression and therapy response. Therefore, understanding what regulates the TME immune compartment is vital. Here we show that microbiota signals program mononuclear phagocytes in the TME toward immunostimulatory monocytes and dendritic cells (DCs). Single-cell RNA sequencing revealed that absence of microbiota skews the TME toward pro-tumorigenic macrophages. Mechanistically, we show that microbiota-derived stimulator of interferon genes (STING) agonists induce type I interferon (IFN-I) production by intratumoral monocytes to regulate macrophage polarization and natural killer (NK) cell-DC crosstalk. Microbiota modulation with a high-fiber diet triggered the intratumoral IFN-I-NK cell-DC axis and improved the efficacy of immune checkpoint blockade (ICB). We validated our findings in individuals with melanoma treated with ICB and showed that the predicted intratumoral IFN-I and immune compositional differences between responder and non-responder individuals can be transferred by fecal microbiota transplantation. Our study uncovers a mechanistic link between the microbiota and the innate TME that can be harnessed to improve cancer therapies.