The biochemical paradigm for carbon monoxide (CO) is driven by the century-old Warburg hypothesis: CO alters O₂-dependent functions by binding heme proteins in competitive relation to 1/oxygen partial pressure (PO₂). High PO₂ thus hastens CO elimination and toxicity resolution, but with more O₂, CO-exposed tissues paradoxically experience less oxidative stress. To help resolve this paradox we tested the Warburg hypothesis using a highly sensitive gas-reduction method to track CO uptake and elimination in brain, heart, and skeletal muscle in situ during and after exogenous CO administration. We found that CO administration does increase tissue CO concentration, but not in strict relation to 1/PO₂. Tissue gas uptake and elimination lag behind blood CO as predicted, but 1/PO₂ vs. [CO] fails even at hyperbaric PO₂. Mechanistically, we established in the brain that cytosol heme concentration increases 10-fold after CO exposure, which sustains intracellular CO content by providing substrate for heme oxygenase (HO) activated after hypoxia when O₂ is resupplied to cells rich in reduced pyridine nucleotides. We further demonstrate by analysis of CO production rates that this heme stress is not due to HO inhibition and that heme accumulation is facilitated by low brain PO₂. The latter becomes rate limiting for HO activity even at physiological PO₂, and the heme stress leads to doubling of brain HO-1 protein. We thus reveal novel biochemical actions of both CO and O₂ that must be accounted for when evaluating oxidative stress and biological signaling by these gases.