Mycobacterium tuberculosis is thought to undergo transformation into its non-replicating persistence state under the influence of hypoxia or nitric oxide (NO). This transformation is thought to be mediated via two sensor histidine kinases, DosS and DosT, each of which contains two GAF domains that are responsible for detecting oxygen tension. In this study we determined the crystal structures of the first GAF domain (GAF-A) of DosS, which shows an interaction with a heme. A b-type heme was embedded in a hydrophobic cavity of the GAF-A domain and was roughly perpendicular to the beta-sheet of the GAF domain. The heme iron was liganded by His-149 at the proximal heme axial position. The iron, in the oxidized form, was six-coordinated with a water molecule at the distal position. Upon reduction, the iron, in ferrous form, was five-coordinated, and when the GAF domain was exposed to atmospheric O(2), the ferrous form was oxidized to generate the Met form rather than a ferrous O(2)-bound form. Because the heme is isolated inside the GAF domain, its accessibility is restricted. However, a defined hydrogen bond network found at the heme site could accelerate the electron transferability and would explain why DosS was unable to bind O(2). Flavin nucleotides were shown to reduce the heme iron of DosS while NADH was unable to do so. These results suggest that DosS is a redox sensor and detects hypoxic conditions by its reduction.