Many bacteria contain cytoplasmic chemoreceptors that lack sensor domains. Here, we demonstrate that such cytoplasmic receptors found in 8 different bacterial and archaeal phyla genetically couple to metalloproteins related to β-lactamases and nitric oxide reductases. We show that this oxygen-binding di-iron protein (ODP) acts as a sensor for chemotactic responses to both iron and oxygen in the human pathogen Treponema denticola (Td). The ODP di-iron site binds oxygen at high affinity to reversibly form an unusually stable μ-peroxo adduct. Crystal structures of ODP from Td and the thermophile Thermotoga maritima (Tm) in the FeIII₂-O₂2−, ZnII, and apo states display differences in subunit association, conformation, and metal coordination that indicate potential mechanisms for sensing. In reconstituted systems, iron-peroxo ODP destabilizes the phosphorylated form of the receptor-coupled histidine kinase CheA, thereby providing a biochemical link between oxygen sensing and chemotaxis in diverse prokaryotes, including anaerobes of ancient origin.