Increased tryptophan (Trp) catabolism in the tumor microenvironment (TME) can mediate immune suppression by upregulation of interferon (IFN)-γ-inducible indoleamine 2,3-dioxygenase (IDO1) and/or ectopic expression of the predominantly liver-restricted enzyme tryptophan 2,3-dioxygenase (TDO). Whether these effects are due to Trp depletion in the TME or mediated by the accumulation of the IDO1 and/or TDO (hereafter referred to as IDO1/TDO) product kynurenine (Kyn) remains controversial. Here we show that administration of a pharmacologically optimized enzyme (PEGylated kynureninase; hereafter referred to as PEG-KYNase) that degrades Kyn into immunologically inert, nontoxic and readily cleared metabolites inhibits tumor growth. Enzyme treatment was associated with a marked increase in the tumor infiltration and proliferation of polyfunctional CD8+ lymphocytes. We show that PEG-KYNase administration had substantial therapeutic effects when combined with approved checkpoint inhibitors or with a cancer vaccine for the treatment of large B16-F10 melanoma, 4T1 breast carcinoma or CT26 colon carcinoma tumors. PEG-KYNase mediated prolonged depletion of Kyn in the TME and reversed the modulatory effects of IDO1/TDO upregulation in the TME.