The efficacy of the anti-cancer immunomodulatory agent cyclophosphamide (CTX) relies on intestinal bacteria. How and which relevant bacterial species are involved in tumor immunosurveillance, and their mechanism of action are unclear. Here, we identified two bacterial species, Enterococcus hirae and Barnesiella intestinihominis that are involved during CTX therapy. Whereas E. hirae translocated from the small intestine to secondary lymphoid organs and increased the intratumoral CD8/Treg ratio, B. intestinihominis accumulated in the colon and promoted the infiltration of IFN-γ-producing γδT cells in cancer lesions. The immune sensor, NOD2, limited CTX-induced cancer immunosurveillance and the bioactivity of these microbes. Finally, E. hirae and B. intestinihominis specific-memory Th1 cell immune responses selectively predicted longer progression-free survival in advanced lung and ovarian cancer patients treated with chemo-immunotherapy. Altogether, E. hirae and B. intestinihominis represent valuable “oncomicrobiotics” ameliorating the efficacy of the most common alkylating immunomodulatory compound.