The evolutionary relationships among species of the family Pseudomonadaceae were examined based on 255 available genomes representing >85 % of the species from this family. In a phylogenetic tree based on concatenated sequences of 118 core proteins, most species of the genus Pseudomonas grouped within one large cluster which also included members of the genera Azotobacter and Azomonas . Within this large cluster 18–30 clades/subclades of species of the genus Pseudomonas consisting of between 1 and 36 species, were observed. However, a number of species of the genus Pseudomonas branched outside of this main cluster and were interspersed among other genera of the family Pseudomonadaceae . This included a strongly supported clade (Pertucinogena clade) consisting of 19 mainly halotolerant species. The distinctness of this clade from all other members of the family Pseudomonadaceae is strongly supported by 24 conserved signature indels (CSIs) in diverse proteins that are exclusively found in all members of this clade. Nine uncharacterized members of the genus Pseudomonas also shared these CSIs and they branched within the Pertucinogena clade, indicating their affiliation to this clade. On the basis of the strong evidence supporting the distinctness of the Pertucinogena clade, we are proposing transfer of species from this clade into a novel genus Halopseudomonas gen. nov. Pseudomonas caeni also branches outside of the main cluster and groups reliably with Oblitimonas alkaliphila and Thiopseudomonas denitrificans . Six identified CSIs are uniquely shared by these three species and we are proposing their integration into the emended genus Thiopseudomonas , which has priority over the name Oblitimonas . We are also proposing transfer of the deep-branching Pseudomonas hussainii , for which 22 exclusive CSIs have been identified, into the genus Atopomonas gen. nov. Lastly, we present strong evidence that the species Pseudomonas cissicola and Pseudomonas geniculata are misclassified into the genus Pseudomonas and that they are specifically related to the genera Xanthomonas and Stenotrophomonas , respectively. In addition, we are also reclassifying ‘Pseudomonas acidophila’ as Paraburkholderia acidicola sp. nov. (Type strain: G-6302=ATCC 31363=BCRC 13035).