Mat-forming benthic cyanobacteria are widespread throughout New Zealand rivers, and their ingestion has been linked to animal poisonings. In this study, potentially toxic benthic cyanobacterial proliferations were collected from 21 rivers and lakes throughout New Zealand. Each environmental sample was screened for anatoxins using liquid chromatography-MS (LC-MS). Thirty-six cyanobacterial strains were isolated and cultured from these samples. A polyphasic approach was used to identify each isolate; this included genotypic analyses [16S rRNA gene sequences and intergenic spacer (ITS)] and morphological characterization. Each culture was analysed for anatoxins using LC-MS and screened for microcystin production potential using targeted PCR. The morphospecies Phormidium autumnale was found to be the dominant cyanobacterium in mat samples. Polyphasic analyses revealed multiple slight morphological variants within the P. autumnale clade and highlighted the difficulties in identifying Oscillatoriaceae. Only one morphospecies (comprising the two strains CYN52 and CYN53) of P. autumnale was found to produce anatoxins. These strains formed their own clade based on partial 16S rRNA gene sequences. These data indicate that benthic P. autumnale mats are composed of multiple morphospecies and toxin production is dependent on the presence of toxin-producing genotypes. Further cyanobacteria are also characterized, including Phormidium murrayi, which was identified for the first time outside of Antarctica.