Viruses and their hosts can undergo coevolutionary arms races where hosts evolve increased resistance and viruses evolve counter-resistance. Given these arms race dynamics (ARD), both players are predicted to evolve along a single trajectory as more recently evolved genotypes replace their predecessors. By coupling phenotypic and genomic analyses of coevolving populations of bacteriophage lambda and Escherichia coli, we find conflicting evidence for ARD. Virus-host infection phenotypes fit the ARD model, yet genomic analyses revealed fluctuating selection dynamics (FSD). Rather than coevolution unfolding along a single trajectory, cryptic genetic variation emerges and is maintained at low frequency for generations until it eventually supplants dominant lineages. These observations suggest a hybrid ‘leapfrog’ dynamic, revealing weaknesses in the predictive power of standard coevolutionary models. The findings shed light on the mechanisms that structure coevolving ecological networks and reveal the limits of using phenotypic or genomic data alone to differentiate coevolutionary dynamics.