Heterotrophic bacteria are the major prokaryotic component of the Baltic Sea ice microbiome, and it is postulated that phages are among their major parasites. In this study, we sequenced the complete genomes of six earlier reported phage isolates from the Baltic Sea ice infecting Shewanella sp. and Flavobacterium sp. hosts as well as characterized the phage-host interactions. Based on the genome sequences, the six phages were classified into five new genera. Only two phages, 1/4 and 1/40, both infecting Shewanella sp. strains, showed significant nucleotide sequence similarity to each other and could be grouped into the same genus. These two phages are also related to Vibrio-specific phages sharing approximately 25% of the predicted gene products. Nevertheless, cross-titrations showed that the cold-active phages studied are host specific: none of the seven additionally tested, closely related Shewanella strains served as hosts for the phages. Adsorption experiments of two Shewanella phages, 1/4 and 3/49, conducted at 4 °C and at 15 °C revealed relatively fast adsorption rates that are, for example, comparable with those of phages infective in mesophilic conditions. Despite the small number of Shewanella phages characterized here, we could already find different types of phage-host interactions including a putative abortive infection.