The taxonomy of cyanobacteria currently faces the challenge of overhauling the traditional system to better reflect the results of phylogenetic analyses. In the present study, we assessed the phylogenetic position, morphological variability, ability to produce the toxin nodularin, and source habitat of 17 benthic and soil isolates of Nodularia. A combined analysis of two loci (partial 16S rRNA gene and rbcLX region) confirmed the genus as a monophyletic unit and the close relationship of its members. However, the taxonomic resolution at the subgeneric level was extremely problematic. The phylogenetic clustering did not show any reasonable congruence with either morphological or ecological features commonly used to separate taxa in heterocytous cyanobacteria. Despite the near phylogenetic similarity of planktonic, benthic and soil Nodularia strains, we did not find any new nodularin-producing strains among the non-planktonic isolates. The relatively low variability in conserved molecular markers within the genus Nodularia exemplifies the limitations of the currently accepted taxonomic workflow and polyphasic approach. Elucidation of mechanisms that drive the phenotypic variability in such groups presents a major challenge in cyanobacterial research.