Soluble guanylate cyclases (sGCs) function as heme sensors that selectively bind nitric oxide (NO), triggering reactions essential to animal physiology. Recent discoveries place sGCs in the H-NOX family (heme nitric oxide/oxygen-binding domain), which includes bacterial proteins from aerobic and anaerobic organisms. Some H-NOX proteins tightly bind oxygen (O2), whereas others show no measurable affinity for O2, providing the basis for selective NO signaling in aerobic cells. Using a series of wild-type and mutant H-NOXs, we established a molecular basis for ligand discrimination. A distal pocket tyrosine is requisite for O2 binding in the H-NOX family. These data suggest that sGC uses a kinetic selection against O2; we propose that the O2 dissociation rate in the absence of this tyrosine is fast and that a stable O2 complex does not form.