The genus Polynucleobacter (family Burkholderiaceae) is phylogenetically subdivided into at least four subclusters. One of those, subcluster PnecC, was recognized as a cryptic species complex. Here we test by comparative genome analyses whether subcluster PnecD, currently solely represented by the species Polynucleobactercosmopolitanus, also represents such a cryptic species complex. The genome sequences of the two P. cosmopolitanus strains, MWH-MoIso2(T) and MWH-VicM1, were determined. The latter strain was also characterized in the previous description of P. cosmopolitanus. These two strains originate from a temperate lake located in Austria and from the large tropical Lake Victoria located in East Africa, respectively. Strains MWH-MoIso2(T) and MWH-VicM1 possess quite small genomes of 1.78 and 1.63 Mbp, respectively, and share similar G+C values of 44.1 and 43.1 mol%, respectively. Both strains encode only a single copy of the ribosomal operon, and their 16S rRNA genes differ only in four positions, equalling a sequence similarity of 99.74 %. Both genomes possess characteristics indicating evolutionary genome streamlining, such as high coding densities of 93.9 and 94.6 % of bases, respectively. Average nucleotide identity (ANI) comparisons of the genomes of the two strains resulted in a value of 78.4 %, suggesting that each of the strains represents a separate species. Our investigation suggests that PnecD represents an additional cryptic species complex within the genus Polynucleobacter that was not resolved by 16S rRNA gene sequence analyses. We propose reclassification of strain MWH-VicM1 as Polynucleobacter victoriensis sp. nov., with type strain MWH-VicM1(T)(=DSM 21486(T)=JCM 32005(T)).