Evaluating the importance of coevolution for a wide range of evolutionary questions, such as the role parasites play in the evolution of sexual reproduction, requires that we understand the genetic basis of coevolutionary interactions. Despite its importance, little progress has been made identifying the genetic basis of coevolution, largely because we lack tools designed specifically for this purpose. Instead, coevolutionary studies are often forced to re-purpose single species techniques. Here, we propose a novel approach for identifying the genes mediating locally adapted coevolutionary interactions that relies on spatial correlations between genetic marker frequencies in the interacting species. Using individual-based multi-locus simulations, we quantify the performance of our approach across a range of coevolutionary genetic models. Our results show that when one species is strongly locally adapted to the other and a sufficient number of populations can be sampled, our approach accurately identifies functionally coupled host and parasite genes. Although not a panacea, the approach we outline here could help to focus the search for coevolving genes in a wide variety of well-studied systems for which substantial local adaptation has been demonstrated.