Heme-Nitric oxide and Oxygen binding protein domains (H-NOX) are found in signaling pathways of both prokaryotes and eukaryotes and share sequence homology with soluble guanylate cyclase, the mammalian NO receptor. In bacteria, H-NOX is associated with kinase or methyl accepting chemotaxis domains. In the O2-sensor of the strict anaerobe Caldanaerobacter tengcongensis (Ct H-NOX) the heme appears highly distorted after O2 binding, but the role of heme distortion in allosteric transitions was not yet evidenced. Here, we measure the dynamics of the heme distortion triggered by the dissociation of diatomics from Ct H-NOX using transient electronic absorption spectroscopy in the picosecond to millisecond time range. We obtained a spectroscopic signature of the heme flattening upon O2 dissociation. The heme distortion is immediately (<1 ps) released after O2 dissociation to produce a relaxed state. This heme conformational change occurs with different proportions depending on diatomics as follows: CO < NO < O2. Our time-resolved data demonstrate that the primary structural event of allostery is the heme distortion in the Ct H-NOX sensor, contrastingly with hemoglobin and the human NO receptor, in which the primary structural events are respectively the motion of the proximal histidine and the rupture of the iron-histidine bond.