The tumor microenvironment (TME) presents differential selective pressure (DSP) that favors the growth of cancer cells, and monovalent therapy is often inadequate in reversing the cancer cell dominance in the TME. In this work, we introduce bacteria as a foreign species to the TME and explore combinatorial treatment strategies to alter DSP for tumor eradication. We show that cancer-selective chemotherapeutic agents and fasting can provide a strong selection pressure against tumor growth in the presence of bacteria. Moreover, we show that an immunogenic drug (oxaliplatin), but not a non-immunogenic one (5-FU), synergizes with the bacteria to activate both the innate and adaptive immunity in the TME, resulting in complete tumor remission and a sustained anti-tumor immunological memory in mice. The combination of oxaliplatin and bacteria greatly enhances the co-stimulatory and antigen-presenting molecules on antigen-presenting cells, which in turn bridge the cytotoxic T cells for cancer-cell killing. Our findings indicate that rational combination of bacterial therapy and immunogenic chemotherapy can promote anticancer immunity against the immunosuppressive TME.