Heme-nitric oxide/oxygen (H-NOX) binding domains are a recently discovered family of heme-based gas sensor proteins that are conserved across eukaryotes and bacteria. Nitric oxide (NO) binding to the heme cofactor of H-NOX proteins has been implicated as a regulatory mechanism for processes ranging from vasodilation in mammals to communal behavior in bacteria. A key molecular event during NO-dependent activation of H-NOX proteins is rupture of the heme-histidine bond and formation of a five-coordinate nitrosyl complex. Although extensive biochemical studies have provided insight into the NO activation mechanism, precise molecular-level details have remained elusive. In the present study, high-resolution crystal structures of the H-NOX protein from Shewanella oneidensis in the unligated, intermediate six-coordinate and activated five-coordinate, NO-bound states are reported. From these structures, it is evident that several structural features in the heme pocket of the unligated protein function to maintain the heme distorted from planarity. NO-induced scission of the iron-histidine bond triggers structural rearrangements in the heme pocket that permit the heme to relax toward planarity, yielding the signaling-competent NO-bound conformation. Here, we also provide characterization of a nonheme metal coordination site occupied by zinc in an H-NOX protein.