Antagonistic relationships such as those between bacteria and their lytic phages enhance genomic diversity through a coevolutionary arms race which shapes genomic architecture and population composition. Mutations that confer phage resistance in the abundant marine cyanobacterium, Prochlorococcus, occur primarily in genomic islands in cell surface related genes that prevent adsorption of phages to the cell. A fitness cost often accompanies phage-resistance. Implicit in the arms race model is the ability of phage mutants to overcome resistance of their hosts, yet little is known of the prevalence of such resistance-breaking mutants and their effect on phage genomes and fitness. We therefore attempted to isolate T7-like cyanopodovirus mutants that infect previously isolated phage-resistant Prochlorococcus strains. Phage mutations were found in genes implicated, by homology analysis, in tail assembly and structure. Exploration of other T7-like cyanopodovirus genomes and viral metagenomes reveals that the arms race enhances phage genomic diversity preferentially in resistance-breaking genes. Two phenotypic classes were found among phage mutants: either those with a small fitness gain on both their original and new hosts; or a large fitness gain on the new host accompanied by a cost of decreased specificity. Overall, resistance-breaking mutants were rare and in most interactions undetectable, suggesting that the arms race alone cannot explain coexistence in this system. Rather we propose that coexistence is also maintained by fluctuating selection dynamics that are superimposed on a background of a coevolutionary arms-race that increases diversity of both hosts and phages.