The coevolutionary arms race between host resistance and parasite infectivity has a central role in the evolution of host-parasite relationships, also in the microbial world, but empirical evidence describing long-term host-pathogen dynamics in nature is still scarce. Yet, from applied perspective, understanding the antagonistic evolution of phage-bacterium relationship in long timescales is crucial for development of phage therapy applications. We studied the coevolution of phage-bacterium interactions in aquaculture during 2007-2014 using the fish pathogen Flavobacterium columnare as a target host species. Phage isolation time compared to bacterial host had a significant effect on infectivity. All bacteria were resistant to phages from 3-4 years from the past, and on the other hand 95.5% of bacteria were susceptible to phages from 4-5 years in the future. In this locally adapting population, evolution of bacterial resistance over several years caused also directional selection for phage infectivity and host range. Genome sequencing of the phages revealed that in response to bacterial resistance, phages counter-adapt and regain infectivity via mutations in the (putative) tail proteins and via incorporation of new DNA in the genome. Our study underlines that whereas bacteria evolve resistance, arms race competition can lead to increased host range of the phage at long time scales. This study can also help to understand how phage therapy should be designed to maintain sufficient efficiency in field conditions.