A collection of Pseudomonas strains was isolated in different regions of Tunisia in the period 2016–2017 from the fruits and leaves of Citrus sinensis cv. ‘Valencia Late’ and Citrus limon cv. ‘Eureka’ plants with symptoms of blast and black pit disease. A phylogenetic analysis of the housekeeping gene rpoD was used for strain identification at the species level. The results demonstrated the affiliation of these strains with the genus Pseudomonas and revealed the presence of 11 strains representing two putative new species in two monophyletic branches. These strains were analyzed morphologically and genotypically by multilocus sequence analyses of the rpoD, gyrB and 16S rRNA (rrs) gene sequences, and their phenotypic characteristics by API 20NE and Biolog GEN III. Plant pathogenic properties were confirmed on fruits and detached leaves of C. limon cv. ‘Eureka’. Fatty acids and WC MALDI-TOF MS major protein profiles were determined. The genomes of both representatives were sequenced. The average nucleotide index and genome-to-genome distance from KC12T and E10BT are below the cut-off established for a described species. These results support the conclusion that the strains KC12T, KC17, KC20, KC22, KC24A, KC25 and KC26 represent a novel species of Pseudomonas, for which the name of Pseudomonas kairouanensis is proposed. The type strain is KC12T (=CECT9766 and CFBP 8662). The strains E10BT, E10AB, E10CB1 and Iy3BA represent another novel species of Pseudomonas for which the name of Pseudomonas nabeulensis is proposed; the type strain is E10BT (=CECT9765 and CFBP 8661).