Prochlorococcus is an abundant marine cyanobacterium that grows rapidly in the environment and contributes significantly to global primary production. This cyanobacterium coexists with many cyanophages in the oceans, likely aided by resistance to numerous co-occurring phages. Spontaneous resistance occurs frequently in Prochlorococcus and is often accompanied by a pleiotropic fitness cost manifested as either a reduced growth rate or enhanced infection by other phages. Here, we assessed the fate of a number of phage-resistant Prochlorococcus strains, focusing on those with a high fitness cost. We found that phage-resistant strains continued evolving toward an improved growth rate and a narrower resistance range, resulting in lineages with phenotypes intermediate between those of ancestral susceptible wild-type and initial resistant substrains. Changes in growth rate and resistance range often occurred in independent events, leading to a decoupling of the selection pressures acting on these phenotypes. These changes were largely the result of additional, compensatory mutations in noncore genes located in genomic islands, although genetic reversions were also observed. Additionally, a mutator strain was identified. The similarity of the evolutionary pathway followed by multiple independent resistant cultures and clones suggests they undergo a predictable evolutionary pathway. This process serves to increase both genetic diversity and infection permutations in Prochlorococcus populations, further augmenting the complexity of the interaction network between Prochlorococcus and its phages in nature. Last, our findings provide an explanation for the apparent paradox of a multitude of resistant Prochlorococcus cells in nature that are growing close to their maximal intrinsic growth rates.