Hemoglobins are found in organisms from every major phylum and subserve life-sustaining respiratory functions across a broad continuum. Sustainable aerobic respiration in mammals and birds relies on the regulated delivery of oxygen (O2) and nitric oxide (NO) bioactivity by hemoglobin, through reversible binding of NO and O2 to hemes as well as S-nitrosylation of cysteine thiols (SNO synthase activity). In contrast, bacterial and yeast flavohemoglobins function in vivo as denitrosylases (O2 nitroxylases), and some multimeric, invertebrate hemoglobins function as deoxygenases (Cys-dependent NO dioxygenases), which efficiently consume rather than deliver NO and O2, respectively. Analogous mechanisms may operate in plants. Bacteria and fungi deficient in flavohemoglobin show compromised virulence in animals that results from impaired resistance to NO, whereas animals and humans deficient in S-nitrosylated Hb exhibit altered vasoactivity. NO-related functions of hemoglobins center on reactions with ferric (FeIII) heme iron, which is exploited in enzymatic reactions that address organismal requirements for delivery or detoxification of NO and O2. Delivery versus detoxification of NO/O2 is largely achieved through structural changes and amino acid rearrangements within the heme pockets, thereby influencing the propensity for heme/cysteine thiol redox coupling. Additionally, the behavior exhibited by hemoglobin in vivo may be profoundly dependent both on the abundance of NO and O2 and on the allosteric effects of heterotropic ligands. Here we review well-documented examples of redox interactions between NO and hemoglobin, with an emphasis on biochemical mechanisms and physiological significance.