The FixL proteins are biological oxygen sensors that restrict the expression of specific genes to hypoxic conditions. FixL’s oxygen-detecting domain is a heme binding region that controls the activity of an attached histidine kinase. The FixL switch is regulated by binding of oxygen and other strong-field ligands. In the absence of bound ligand, the heme domain permits kinase activity. In the presence of bound ligand, this domain turns off kinase activity. Comparison of the structures of two forms of the Bradyrhizobium japonicum FixL heme domain, one in the “on” state without bound ligand and one in the “off” state with bound cyanide, reveals a mechanism of regulation by a heme that is distinct from the classical hemoglobin models. The close structural resemblance of the FixL heme domain to the photoactive yellow protein confirms the existence of a PAS structural motif but reveals the presence of an alternative regulatory gateway.