The capacity to fix nitrogen is widely distributed in phyla of Bacteria and Archaea but has long been considered to be absent from the Pseudomonas genus. We report here the complete genome sequencing of nitrogen-fixing root-associated Pseudomonas stutzeri A1501. The genome consists of a single circular chromosome with 4,567,418 bp. Comparative genomics revealed that, among 4,146 protein-encoding genes, 1,977 have orthologs in each of the five other Pseudomonas representative species sequenced to date. The genome contains genes involved in broad utilization of carbon sources, nitrogen fixation, denitrification, degradation of aromatic compounds, biosynthesis of polyhydroxybutyrate, multiple pathways of protection against environmental stress, and other functions that presumably give A1501 an advantage in root colonization. Genetic information on synthesis, maturation, and functioning of nitrogenase is clustered in a 49-kb island, suggesting that this property was acquired by lateral gene transfer. New genes required for the nitrogen fixation process have been identified within the nif island. The genome sequence offers the genetic basis for further study of the evolution of the nitrogen fixation property and identification of rhizosphere competence traits required in the interaction with host plants; moreover, it opens up new perspectives for wider application of root-associated diazotrophs in sustainable agriculture.