While filamentous cyanobacteria play a crucial role in food web dynamics and biogeochemical cycling of many aquatic ecosystems around the globe, the knowledge regarding phages infecting them is limited. Here we describe the complete genome of the virulent cyanophage vB_AphaS-CL131 (CL 131), a Siphoviridae phage that infects filamentous diazotrophic bloom forming cyanobacterium Aphanizomenon flos-aquae in the brackish Baltic Sea. CL 131 features a 112793 bp dsDNA genome, encompassing 149 putative open reading frames (ORFs), of which the majority (86%) lack sequence homology to genes with known functions in other bacteriophages or bacteria. Phylogenetic analysis revealed that CL 131 possibly represents a new evolutionary lineage within the group of cyanophages infecting filamentous cyanobacteria, which form a separate cluster compared to phages infecting unicellular cyanobacteria. CL 131 encodes a putative type V-U2 CRISPR-Cas system with one spacer (out of 10) targeting a DNA primase pseudogene in a cyanobacterium and a putative type II toxin-antitoxin system, consisting of GNAT family N-acetyltransferase and a protein of unknown function containing the PRK09726 domain (characteristic of HipB antitoxins). Comparison of CL 131 proteins to reads from Baltic Sea and other available fresh- and brackish-water metagenomes and analysis of CRISPR-Cas arrays in publicly available A. flos-aquae genomes demonstrated that phages similar to CL 131 are present and dynamic in the Baltic Sea and share common history with their hosts dating back at least several decades. In addition, different CRISPR-Cas systems within individual A. flos-aquae genomes targeted several sequences in the CL 131 genome, including genes related to virion structure and morphogenesis. Altogether, these findings revealed new genomic information for exploring viral diversity and provide a model system for investigation of virus-host interactions in filamentous cyanobacteria.Importance The genomic characterization of novel cyanophage vB_AphaS-CL131 and the analysis of its genomic features in the context of other viruses, metagenomic data and host CRISPR-Cas systems contribute toward better understanding of aquatic viral diversity and distribution in general and brackish water cyanophages infecting filamentous diazotrophic cyanobacteria in the Baltic Sea in particular. The results of this study revealed previously undescribed features of cyanophage genomes (e.g. self-excising intein-containing putative dCTP deaminase, putative cyanophage-encoded CRISPR-Cas and toxin-antitoxin systems) and can therefore be used to predict potential interactions between bloom-forming cyanobacteria and their cyanophages.