Fitness costs associated with resistance or virulence genes are thought to play a key role in determining the dynamics of gene-for-gene (GFG) host-parasite coevolution. However, the nature of interactions between fitness effects of multiple resistance or virulence genes (epistasis) has received less attention. To examine effects of the functional form of epistasis on the dynamics of GFG host-parasite coevolution we modified a classic multilocus GFG model framework. We show that the type of epistasis between virulence genes largely determines coevolutionary dynamics, and that coevolutionary fluctuations are more likely with acceleratingly costly (negative) than with linear or deceleratingly costly (positive) epistasis. Our results demonstrate that the specific forms of interaction between multiple resistance or virulence genes are a crucial determinant of host-parasite coevolutionary dynamics.