We present here the analysis of the whole-genome sequence of Pseudomonas stutzeri strain DSM4166, a diazotrophic isolate from the rhizosphere of a Sorghum nutans cultivar. To our knowledge, this is the second genome to be sequenced for P. stutzeri. The availability and analysis of the genome provide insight into the evolution of the nitrogen fixation property and identification of rhizosphere competence traits required in interactions with host plants.