There is a long-standing interest in understanding host-parasite coevolutionary dynamics and associated fitness effects. Increasing amounts of genomic data for both interacting species offer a promising source to identify candidate loci and to infer the main parameters of the past coevolutionary history. However, so far no method exists to perform the latter. By coupling a gene-for-gene model with coalescent simulations, we first show that three types of biological costs, namely, resistance, infectivity and infection, define the allele frequencies at the internal equilibrium point of the coevolution model. These in return determine the strength of selective signatures at the coevolving host and parasite loci. We apply an Approximate Bayesian Computation (ABC) approach on simulated datasets to infer these costs by jointly integrating host and parasite polymorphism data at the coevolving loci. To control for the effect of genetic drift on coevolutionary dynamics, we assume that 10 or 30 repetitions are available from controlled experiments or several natural populations. We study two scenarios: 1) the cost of infection and population sizes (host and parasite) are unknown while costs of infectivity and resistance are known, and 2) all three costs are unknown while populations sizes are known. Using the ABC model choice procedure, we show that for both scenarios, we can distinguish with high accuracy pairs of coevolving host and parasite loci from pairs of neutrally evolving loci, though the statistical power decreases with higher cost of infection. The accuracy of parameter inference is high under both scenarios especially when using both host and parasite data because parasite polymorphism data do inform on costs applying to the host and vice-versa. As the false positive rate to detect pairs of genes under coevolution is small, we suggest that our method complements recently developed methods to identify host and parasite candidate loci for functional studies.