Two strains of Gram-negative bacteria isolated from soil by selective enrichment with nitroaromatics were subjected to a polyphasic taxonomic study. On the basis of 16S rRNA gene sequence analysis, the two strains were found to belong to the genus Pseudomonas, within the Gammaproteobacteria. Strain 1B4T shared the highest sequence similarity with Pseudomonas koreensis DSM 16610T (99.5%) and Pseudomonas jessenii CCM 4840T (99.3%), and strain 2B2T with Pseudomonas asplenii DSM 17133T (98.9%), Pseudomonas fuscovaginae DSM 7231T (98.9%) and Pseudomonas putida DSM 291T (98.7%). On the basis of phylogenetic analysis, DNA-DNA hybridization and phenotype, including chemotaxonomic characteristics, two novel species, Pseudomonas moraviensis sp. nov. with the type strain 1B4T (=CCM 7280T=DSM 16007T) and Pseudomonas vranovensis sp. nov. with the type strain 2B2T (=CCM 7279T=DSM 16006T), are proposed. The description of P. asplenii was emended on the basis of additional data obtained in this study.