Pseudomonas is a large and diverse genus of Gammaproteobacteria. To provide a framework for discovery of evolutionary and taxonomic relationships of these bacteria, we compared the genomes of type strains of 163 species and 3 additional subspecies of Pseudomonas, including 118 genomes sequenced herein. A maximum likelihood phylogeny of the 166 type strains based on protein sequences of 100 single-copy orthologous genes revealed thirteen groups of Pseudomonas, composed of two to sixty three species each. Pairwise average nucleotide identities and alignment fractions were calculated for the data set of the 166 type strains and 1224 genomes of Pseudomonas available in public databases. Results revealed that 394 of the 1224 genomes were distinct from any type strain, suggesting that the type strains represent only a fraction of the genomic diversity of the genus. The core genome of Pseudomonas was determined to contain 794 genes conferring primarily housekeeping functions. The results of this study provide a phylogenetic framework for future studies aiming to resolve the classification and phylogenetic relationships, identify new gene functions and phenotypes, and explore the ecological and metabolic potential of the Pseudomonas spp.