In sub-Saharan Africa, invasive nontyphoid Salmonella (NTS) infection is a common and often fatal complication of Plasmodium falciparum infection. Induction of heme oxygenase-1 (HO-1) mediates tolerance to the cytotoxic effects of heme during malarial hemolysis but might impair resistance to NTS by limiting production of bactericidal reactive oxygen species. We show that co-infection of mice with Plasmodium yoelii 17XNL (Py17XNL) and Salmonella enterica serovar Typhimurium 12023 (Salmonella typhimurium) causes acute, fatal bacteremia with high bacterial load, features reproduced by phenylhydrazine-induced hemolysis or hemin administration. S. typhimurium localized predominantly in granulocytes. Py17XNL, phenylhydrazine and hemin caused premature mobilization of granulocytes from bone marrow with a quantitative defect in the oxidative burst. Inhibition of HO by tin protoporphyrin abrogated the impairment of resistance to S. typhimurium by hemolysis. Thus, a mechanism of tolerance to one infection, malaria, impairs resistance to another, NTS. Furthermore, HO inhibitors may be useful adjunctive therapy for NTS infection in the context of hemolysis.