Between-species coevolution, and in particular antagonistic host-parasite coevolution, is a major process shaping within-species diversity. In this paper we investigate the role of various stochastic processes affecting the outcome of the deterministic coevolutionary models. Specifically, we assess (1) the impact of genetic drift and mutation on the maintenance of polymorphism at the interacting loci, and (2) the change in neutral allele frequencies across the genome of both coevolving species due to co-demographic population size changes. We find that genetic drift decreases the likelihood to observe classic balancing selection signatures, and that for most realistic values of the coevolutionary parameters, balancing selection signatures cannot be seen at the host loci. Further, we reveal that contrary to classic expectations, fast changes in parasite population size due to eco-evo feedbacks can be tracked by the allelic site-frequency spectrum measured at several time points. Changes in host population size are, however, less pronounced and thus not observable. Finally, we also review several understudied stochastic processes occurring in host-parasite coevolution which are of importance to predict maintenance of polymorphism at the underlying loci and the genome-wide nucleotide diversity of host and parasite populations.