Bacteriophage and their bacterial hosts undergo antagonistic coevolution in laboratory experiments, leading to rapid genetic changes. What is less clear is the relevance of these scenarios for the structure and ‘evolution’ of the phage-host network in the environment. We conducted a population genomics study of ~70 cyanomyoviral isolates belonging to one specific population (S-CAM7), isolated from various sites along the California Coast over a four year period. The population showed a core genomic backbone, with clock-like substitution rates, interspersed with distinct variable regions (VRs). The VRs often encode likely structural proteins involved in host attachment and thus may be responding to coevolution. We complemented the genomic data with laboratory coevolution experiments between specific isolates in this population and a host (Synechococcus sp. WH7803). We showed that VRs responded to both coevolution as well as directed evolution to the host through accumulation of SNVs and recombination events in end-point community metagenomes as well as in isolates from these populations. Moreover, we show that many of these mutations alter individual fitness of the bacteriophage and their host-range. Together, our data demonstrate that coevolution is a major driver of genomic diversification in emerging populations of marine bacteriophages. What’s more our time-dependent phylogenetics approach allows us to identify the timescales in which coevolution scenarios play out in the wild.