Many bacteria adapt to microoxic conditions by synthesizing a particular cytochrome c oxidase (cbb3) complex with a high affinity for O2, encoded by the ccoNOQP operon. A survey of genome databases indicates that ccoNOQP sequences are widespread in all sub-branches of Proteobacteria but otherwise are found only in bacteria of the CFB group ( Cytophaga, Flexibacter, Bacteroides). Our analysis of available genome sequences suggests four major strategies of regulating ccoNOQP expression in response to O2. The most widespread strategy involves direct regulation by the O2-responsive protein Fnr. The second strategy involves an O2-insensitive paralogue of Fnr, FixK, whose expression is regulated by the O2-responding FixLJ two-component system. A third strategy of mixed regulation operates in bacteria carrying both fnr and fixLJ-fixKgenes. Another, not yet identified, strategy is likely to operate in the epsilon-Proteobacteria Helicobacter pylori and Campylobacter jejuni which lack fnr and fixLJ-fixK genes. The FixLJ strategy appears specific for the alpha-subclass of Proteobacteria but is not restricted to rhizobia in which it was originally discovered.