Two cyanobacterial strains CHAB5870 and CHAB5871 morphologically identified as Nostoc-like species were isolated from different habitats in China, and they were phylogenetically and taxonomically characterized based on a polyphasic approach combining morphological, ecological, and molecular data. In the 16S rRNA gene phylogeny inferred using maximum likelihood, maximum-parismony, and bayesian inference methods, these two strains clustered within the Pseudoaliinostoc clade. The 16S rRNA gene sequences of these two strains displayed >= 95.5% and <= 98% similarity to Pseudoaliinostoc species, which indicated them to represent new species of the genus Pseudoaliinostoc. Furthermore, the unique pattern of D1-D1 ' and Box-B helix of the 16S-23S rRNA internal transcribed spacer (ITS) secondary structure also revealed that two strains represented novel species. These results supported the establishment of two new Pseudoaliinostoc species with the name P. jiangxiense sp. nov. and P. yunnanense sp. nov.