We investigate the host-parasite coevolution by using the quasi-species model with a frequencydependent fitness landscape. We propose a quasi-species model for the host-parasite coevolution and find the phase diagram for a given set of dynamics parameters by means of a linear stability analysis and numerical solutions. There are four trivial equilibrium points, which are stable or unstable, and one internal equilibrium point, which is unstable or a center-fixed point enclosed by limit cycles, depending on the dynamics parameters. By starting from a random initial condition, we determine the separatrix and the basins of attraction. We also present the corresponding stochastic model for the host-parasite coevolution, and by computer simulation, we find that the stochastic simulation results are consistent with those of the quasi-species model.