Bacteria adjust the composition of their electron transport chain (ETC) to efficiently adapt to oxygen gradients. This involves differential expression of various ETC components to optimize energy generation. In Herbaspirillum seropedicae, reprogramming of gene expression in response to oxygen availability is controlled at the transcriptional level by three Fnr orthologs. Here, we characterised Fnr regulons using a combination of RNA-Seq and ChIP-Seq analysis. We found that Fnr1 and Fnr3 directly regulate discrete groups of promoters (Groups I and II, respectively), and that a third group (Group III) is co-regulated by both transcription factors. Comparison of DNA binding motifs between the three promoter groups suggests Group III promoters are potentially co-activated by Fnr3-Fnr1 heterodimers. Specific interaction between Fnr1 and Fnr3, detected in two-hybrid assays, was dependent on conserved residues in their dimerization interfaces, indicative of heterodimer formation in vivo. The requirements for co-activation of the fnr1 promoter, belonging to Group III, suggest either sequential activation by Fnr3 and Fnr1 homodimers or the involvement of Fnr3-Fnr1 heterodimers. Analysis of Fnr proteins with swapped activation domains provides evidence that co-activation by Fnr1 and Fnr3 at Group III promoters optimises interactions with RNA polymerase to fine-tune transcription in response to prevailing oxygen concentrations.