Diatomic ligand discrimination by soluble guanylyl cyclase (sGC) is paramount to cardiovascular homeostasis and neuronal signaling. Nitric oxide (NO) stimulates sGC activity 200-fold compared with only four-fold by carbon monoxide (CO). The molecular details of ligand discrimination and differential response to NO and CO are not well understood. These ligands are sensed by the heme domain of sGC, which belongs to the heme nitric oxide oxygen (H-NOX) domain family, also evolutionarily conserved in prokaryotes. Here we report crystal structures of the free, NO-bound, and CO-bound H-NOX domains of a cyanobacterial homolog. These structures and complementary mutational analysis in sGC reveal a molecular ruler mechanism that allows sGC to favor NO over CO while excluding oxygen, concomitant to signaling that exploits differential heme pivoting and heme bending. The heme thereby serves as a flexing wedge, allowing the N-terminal subdomain of H-NOX to shift concurrent with the transition of the six- to five-coordinated NO-bound state upon sGC activation. This transition can be modulated by mutations at sGC residues 74 and 145 and corresponding residues in the cyanobacterial H-NOX homolog.