The anaerobic metabolism of the opportunistic pathogen Pseudomonas aeruginosa is important for growth and biofilm formation during persistent infections. The two Fnr-type transcription factors Anr and Dnr regulate different parts of the underlying network in response to oxygen tension and NO. Little is known about all members of the Anr and Dnr regulons and the mediated immediate response to oxygen depletion. Comprehensive transcriptome and bioinformatics analyses in combination with a limited proteome analyses were used for the investigation of the P. aeruginosa response to an immediate oxygen depletion and for definition of the corresponding Anr and Dnr regulons. We observed at first the activation of fermentative pathways for immediate energy generation followed by induction of alternative respiratory chains. A solid position weight matrix model was deduced from the experimentally identified Anr boxes and used for identification of 170 putative Anr boxes in potential P. aeruginosa promoter regions. The combination with the experimental data unambiguously identified 130 new members for the Anr and Dnr regulons. The basis for the understanding of two regulons of P. aeruginosa central to biofilm formation and infection is now defined.