Host-parasite interactions are often characterized by large fluctuations in host population size, and we investigated how such host bottlenecks affected coevolution between a bacterium and a virus. Previous theory suggests that host bottlenecks should provide parasites with an evolutionary advantage, but instead we found that phages were rapidly driven to extinction when coevolving with hosts exposed to large genetic bottlenecks. This was caused by the stochastic loss of sensitive bacteria, which are required for phage persistence and infectivity evolution. Our findings emphasize the importance of feedbacks between ecological and coevolutionary dynamics, and how this feedback can qualitatively alter coevolutionary dynamics.