Knowledge in aquatic virology has been greatly improved by culture-independent methods, yet there is still a critical need for isolating novel phages to identify the large proportion of “unknowns” that dominate metagenomes and for detailed analyses of phage-host interactions. Here, 54 phages infecting Rheinheimera sp. strain BAL341 (Gammaproteobacteria) were isolated from Baltic Sea seawater and characterized through genome content analysis and comparative genomics. The phages showed a myovirus-like morphology and belonged to a novel genus, for which we propose the name Barbavirus. All phages had similar genome sizes and numbers of genes (80 to 84 kb; 134 to 145 genes), and based on average nucleotide identity and genome BLAST distance phylogeny, the phages were divided into five species. The phages possessed several genes involved in metabolic processes and host signaling, such as genes encoding ribonucleotide reductase and thymidylate synthase, phoH, and mazG. One species had additional metabolic genes involved in pyridine nucleotide salvage, possibly providing a fitness advantage by further increasing the phages’ replication efficiency. Recruitment of viral metagenomic reads (25 Baltic Sea viral metagenomes from 2012 to 2015) to the phage genomes showed pronounced seasonal variations, with increased relative abundances of barba phages in August and September synchronized with peaks in host abundances, as shown by 16S rRNA gene amplicon sequencing. Overall, this study provides detailed information regarding genetic diversity, phage-host interactions, and temporal dynamics of an ecologically important aquatic phage-host system.