Biofilms are surface-attached communities of bacteria enclosed in a polysaccharide matrix. Bacteria in a biofilm are extremely resistant to antibiotics. Several recent reports have linked the signaling molecule nitric oxide (NO) with biofilm dispersal. We have previously reported that an H-NOX (heme-nitric oxide/oxygen binding) protein in the biofilm-dwelling bacterium Shewanella woodyi mediates NO-induced biofilm dispersal. In S. woodyi, H-NOX (SwH-NOX) is cocistronic with a gene encoding a dual-functioning diguanylate cyclase/phosphodiesterase enzyme, designated here as HaCE (H-NOX-associated cyclic-di-GMP processing enzyme). Enzymes such as these are responsible for regulating the intracellular concentrations of cyclic-di-GMP, a secondary signaling molecule essential to biofilm formation in bacteria. We have demonstrated that NO-bound SwH-NOX regulates both enzymatic activities of SwHaCE, resulting in decreased cellular cyclic-di-GMP levels and disruption of biofilm formation. Thus, H-NOX/HaCE represents a potential drug target for regulating biofilm formation. In this work, the SwH-NOX surface residues critical for the formation of a protein complex with SwHaCE are identified using nuclear magnetic resonance, fluorescence quenching, and cosedimentation. Enzyme assays confirm this protein-protein interface and its importance for H-NOX/HaCE function.