Soluble guanylate cyclase (sGC) is a nitric oxide (NO)-sensing hemoprotein that has been identified in animals from Drosophila to humans. sGC mediates vasodilation, platelet aggregation and neurotransmission and, unlike many hemoproteins, has the unique characteristic of not binding O2---a property which allows this enzyme to sense NO in an aerobic environment. Using the sGC heme domain as the query sequence in a BLAST search, we have identified multiple, predicted prokaryotic proteins with significant homology to this region. We have cloned and characterized the sGC-like heme domains from Vibrio cholerae and Nostoc punctiforme and find that both of them are similar to sGC and are likely prokaryotic NO-sensors. Both ORFs are found in hi...