Cyanophages are crucial for regulating cyanobacterial populations, but their influence on anatoxin-producing Microcoleus mat dynamics remains unexplored. Here, we use metagenomics to explore phage presence in benthic mats from the Wolastoq|Saint John River (New Brunswick, Canada) and the Eel River (California, USA). We recovered multiple viral-like sequences associated with different putative bacterial hosts, including two cyanophage genomes with apparently different replication strategies. A temperate cyanophage was found integrated in the genomes of Microcoleus sp. 3 recovered from the Eel River and is phylogenetically related to Phormidium phages. We also recovered novel virulent cyanophage genomes from Wolastoq and Eel River mats that were dominated by anatoxin-producing Microcoleus species predicted to be the host. Despite the geographical distance, these genomes have similar sizes (circa 239 kbp) and share numerous orthologous genes with high sequence identity. A considerable reduction of the anatoxin-producing Microcoleus species in Wolastoq mats following the emergence of the virulent phage suggests that phage infections have an important role in limiting the abundance of this toxigenic cyanobacterium and releasing anatoxins into the surrounding water. Our results constitute the first report of cyanophages predicted to infect mat-forming Microcoleus species associated with anatoxin production.