Nitric oxide (NO) is extremely toxic to Clostridium botulinum, but its molecular targets are unknown. Here, we identify a heme protein sensor (SONO) that displays femtomolar affinity for NO. The crystal structure of the SONO heme domain reveals a previously undescribed fold and a strategically placed tyrosine residue that modulates heme-nitrosyl coordination. Furthermore, the domain architertnre of a SONO ortholg cloned from Chlamydomonas reinhardtii indicates that NO signaling though cyclic guanosine monophosphate arose before the origin of multicellular eukaryotes. Our findings have broad implications for understanding bacterial responses to No, as well as for the activation of mammalian No-sensitive guanylyl cyclase.