The excellent-root-colonizing Pseudomonas fluorescens WCS365 was selected previously as the parental strain for the isolation of mutants impaired in root colonization. Transposon mutagenesis of WCS365 and testing for root colonization resulted in the isolation of mutant strain PCL1201, which is approximately 100-fold impaired in competitive tomato root colonization. In this manuscript, we provide evidence that shows that the lack of NADH dehydrogenase I, an enzyme of the aerobic respiratory chain encoded by the nuo operon, is responsible for the impaired root-colonization ability of PCL1201. The complete sequence of the nuo operon (ranging from nuoA to nuoN) of P. fluorescens WCS365 was identified, including the promoter region and a transcriptional terminator consensus sequence downstream of nuoN. It was shown biochemically that PCL1201 is lacking NADH dehydrogenase I activity. In addition, the presence and activity of a second NADH dehydrogenase, encoded by the ndh gene, was identified to our knowledge for the first time in the genus Pseudomonas. Since it was assumed that low-oxygen conditions were present in the rhizosphere, we analyzed the activity of the nuo and the ndh promoters at different oxygen tensions. The results showed that both promoters are up-regulated by low concentrations of oxygen and that their levels of expression vary during growth. By using lacZ as a marker, it was shown that both the nuo operon and the ndh gene are expressed in the tomato rhizosphere. In contrast to the nuo mutant PCL1201, an ndh mutant of WCS365 appeared not to be impaired in competitive root tip colonization.