Soluble guanylate cyclase (sGC) is a nitric oxide- (NO-) sensing hemoprotein that has been found in eukaryotes from Drosophila to humans. Prokaryotic proteins with significant homology to the heme domain of sGC have recently been identified through genomic analysis. Characterization of two of these proteins is reported here. The first is a 181 amino acid protein cloned from Vibrio cholerae (VCA0720) that is encoded in a histidine kinase-containing operon. The ferrous unligated form of VCA0720 is 5-coordinate, high-spin. The CO complex is low-spin, 6-coordinate, and the NO complex is high-spin and 5-coordinate. These ligand-binding properties are very similar to those of sGC. The second protein is the N-terminal 188 amino acids of Tar4 (TtTar4H), a predicted methyl-accepting chemotaxis protein (MCP) from the strict anaerobe Thermoanaerobacter tengcongensis. TtTar4H forms a low-spin, 6-coordinate ferrous-oxy complex, the first of this sGC-related family that binds O2. TtTar4H has ligand-binding properties similar to those of the heme-containing O2 sensors such as AxPDEA1. sGC does not bind O2 despite having a porphyrin with a histidyl ligand like the globins. The results reported here, with sequence-related proteins from prokaryotes but in the same family as the sGC heme domain, show that these proteins have evolved to discriminate between ligands such as NO and O2; hence, we term this family H-NOX domains (heme-nitric oxide/oxygen).