We hypothesized that tumor-associated macrophages (TAMs) are controlled by the diffusible gas carbon monoxide (CO). We demonstrate that induction of apoptosis in lung tumors treated with low doses of CO is associated with increased CD86 expression and activation of mitogen-activated protein kinase (MAPK)/extracellular signal-regulated kinases (Erk) 1/2 pathway in tumor microenvironment. Presence of CD86-positive cells was required for the anti-tumoral effects of CO in established A549 xenografts. We show that the effects of CO on tumor stroma and reprogramming of macrophages towards the anti-tumoral phenotype is mediated by reactive oxygen species (ROS)-dependent activation of MAPK/Erk1/2-c-myc pathway as well as Notch 1-dependent negative feedback on the metabolic enzyme heme oxygenase-1 (HO-1). We find a similar negative correlation between HO-1 and active MAPK-Erk1/2 levels in human lung cancer specimens.