The role of phenotypic plasticity in the evolution of new traits is controversial due to a lack of direct evidence. Phage host range becomes plastic in the presence of restriction-modification (R-M) systems in their hosts. I modeled the evolution of phage host range in the presence of R-M systems. The model makes two main predictions. The first prediction is that the offspring of the first phage to gain a new methylation pattern by infecting a new host make up a disproportionate fraction of the subsequent specialist population, indicating that the plastically produced phenotype is highly predictive of evolutionary outcome. The second prediction is that the first phage to gain this pattern is not always genetically distinct from other phages in the population. Taken together, these results suggest that plasticity could play a causal role on par with mutation during the evolution of phage host range. This uniquely tractable system could enable the first direct test of “plasticity first” evolution.