Pseudomonas aeruginosa is a ubiquitously occurring environmental bacterium and opportunistic pathogen responsible for various acute and chronic infections. Obviously, anaerobic energy generation via denitrification contributes to its ecological success. To investigate the structural basis for the interconnection of the denitrification machinery to other essential cellular processes, we have sought to identify the protein interaction partners of the denitrification enzyme nitrite reductase NirS in the periplasm. We employed NirS as an affinity-purifiable bait to identify interacting proteins in vivo. Results obtained revealed that both the flagellar structural protein FliC and the protein chaperone DnaK form a complex with NirS in the periplasm. The interacting domains of NirS and FliC were tentatively identified. The NirS-interacting stretch of amino acids lies within its cytochrome c domain. Motility assays and ultrastructure analyses revealed that a nirS mutant was defective in the formation of flagella and correspondingly in swimming motility. In contrast, the fliC mutant revealed an intact denitrification pathway. However, deletion of the nirF gene, coding for a heme d1 biosynthetic enzyme, which leads to catalytically inactive NirS, did not abolish swimming ability. This pointed to a structural function for the NirS protein. FliC and NirS were found colocalized with DnaK at the cell surface of P. aeruginosa. A function of the detected periplasmic NirS-DnaK-FliC complex in flagellum formation and motility was concluded and discussed.