Microbial flavohemoglobins (flavoHbs) and hemoglobins (Hbs) show large *NO dioxygenation rate constants ranging from 745 to 2900 microM(-1) s(-1) suggesting a primal *NO dioxygenase (NOD) (EC 1.14.12.17) function for the ancient Hb superfamily. Indeed, modern O2-transporting and storing mammalian red blood cell Hb and related muscle myoglobin (Mb) show vestigial *NO dioxygenation activity with rate constants of 34-89 microM(-1) s(-1). In support of a NOD function, microbial flavoHbs and Hbs catalyze O2-dependent cellular *NO metabolism, protect cells from *NO poisoning, and are induced by *NO exposures. Red blood cell Hb, myocyte Mb, and flavoHb-like activities metabolize *NO in the vascular lumen, muscle, and other mammalian cells, respectively, decreasing *NO signalling and toxicity. HbFe(III)-OO*, HbFe(III)-OONO and protein-caged [HbFe(III)-O**NO2] are proposed intermediates in a reaction mechanism that combines both O-atoms of O2 with *NO to form nitrate and HbFe(III). A conserved Hb heme pocket structure facilitates the dioxygenation reaction and efficient turnover is achieved through the univalent reduction of HbFe(III) by associated reductases. High affinity flavoHb and Hb heme ligands, and other inhibitors, may find application as antibiotics and antitumor agents that enhance the toxicity of immune cell-derived *NO or as vasorelaxants that increase *NO signalling.