Hemoglobins (Hbs) have been characterized from a wide variety of eubacteria, but not from nitrogen-fixing rhizobia. Our search for Hb-like sequences in the Sinorhizobium meliloti genome revealed that a gene coding for a flavohemoglobin (fHb) exists in S. meliloti (SmfHb). Computer analysis showed that SmfHb and Alcaligenes eutrophus fHb are highly similar and could fold into the same tertiary structure. A FNR-like box was detected upstream of the smfhb gene and mapping analysis revealed that the smfhb gene is flanked by nos and fix genes. These observations suggest that smjhb is regulated by the concentration of O2 and that SmfHb functions in some aspects of nitrogen metabolism.