The effectiveness of new cancer therapies such as checkpoint blockade and adoptive cell transfer of activated anti-tumor T cells requires overcoming immunosuppressive tumor microenvironments. We found that the activation of tumor-infiltrating myeloid cells to produce local nitric oxide is a prerequisite for adoptively transferred CD8+ cytotoxic T cells to destroy tumors. These myeloid cells are phenotypically similar to Tip-DCs or nitric oxide- and TNF-producing dendritic cells. The nitric oxide-dependent killing was tempered by coincident arginase 1 expression, which competes with iNOS for arginine, the substrate for nitric oxide production. Depletion of immunosuppressive CSF-1R-dependent arginase 1+ myeloid cells enhanced nitric oxide-dependent tumor killing. Tumor killing via iNOS was independent of the microbiota but dependent on the CD40-CD40L pathway and, in part, lymphotoxin alpha. We extended our findings in mice to uncover a strong correlation between iNOS, CD40 and TNF expression and survival in colorectal cancer patients. Our results identify a network of anti-tumor targets to boost the efficacy of cancer immunotherapies.