Indoleamine 2,3-dioxygenase (IDO) has been implicated in immune evasion by tumors. Upregulation of this tryptophan (Trp)-catabolizing enzyme, in tumor cells and myeloid-derived suppressor cells (MDSCs) within the tumor microenvironment (TME), leads to Trp depletion that impairs cytotoxic T cell responses and survival; however, exact mechanisms remain incompletely understood. We previously reported that a combination therapy of gemcitabine and a superoxide dismutase mimetic promotes anti-tumor immunity in a mouse model of lung cancer by inhibiting MDSCs, enhancing polyfunctional response of CD8+ memory T cells, and extending survival. Here, we show that combination therapy targets IDO signaling, specifically in MDSCs, tumor cells, and CD8+ T cells infiltrating the TME. Deficiency of IDO caused significant reduction in tumor burden, tumor-infiltrating MDSCs, GM-CSF, MDSC survival and infiltration of programmed death receptor-1 (PD-1)-expressing CD8+ T cells compared to controls. IDO-/- MDSCs downregulated nutrient-sensing AMP-activated protein kinase (AMPK) activity, but IDO-/- CD8+ T cells showed AMPK activation associated with enhanced effector function. Our studies provide proof-of-concept for the efficacy of this combination therapy in inhibiting IDO and T cell exhaustion in a syngeneic model of lung cancer and provide mechanistic insights for IDO-dependent metabolic reprogramming of MDSCs that reduces T cell exhaustion and regulates anti-tumor immunity.