Understanding how parasites adapt to changes in host resistance is crucial to evolutionary epidemiology. Experimental studies have demonstrated that parasites are more capable of adapting to gradual, rather than sudden changes in host phenotype, as the latter may require multiple mutations that are unlikely to arise simultaneously. A key, but as yet unexplored factor is precisely how interactions between mutations (epistasis) affect parasite evolution. Here, we investigate this phenomenon in the context of infectivity range, where parasites may experience selection to infect broader sets of genotypes. When epistasis is strongly positive, we find that parasites are unlikely to evolve broader infectivity ranges if hosts exhibit sudden, rather than gradual changes in phenotype, in close agreement with empirical observations. This is due to a low probability of fixing multiple mutations that individually confer no immediate advantage. When epistasis is weaker, parasites are more likely to evolve broader infectivity ranges if hosts make sudden changes in phenotype, which can be explained by a balance between mutation supply and selection. Thus, we demonstrate that both the rate of phenotypic change in hosts and the form of epistasis between mutations in parasites are crucial in shaping the evolution of infectivity range.