Red Queen dynamics, involving coevolutionary interactions between species, are ubiquitous, shaping the evolution of diverse biological systems. To date, information on the underlying selection dynamics and the involved genome regions is mainly available for bacteria-phage systems or only one of the antagonists of a eukaryotic host-pathogen interaction. We add to our understanding of these important coevolutionary interactions using an experimental host-pathogen model, which includes the nematode Caenorhabditis elegans and its pathogen Bacillus thuringiensis We combined experimental evolution with time-shift experiments, in which a focal host or pathogen is tested against a coevolved antagonist from the past, present, or future, followed by genomic analysis. We show that (i) coevolution occurs rapidly within few generations, (ii) temporal coadaptation at the phenotypic level is found in parallel across replicate populations, consistent with antagonistic frequency-dependent selection, (iii) genomic changes in the pathogen match the phenotypic pattern and include copy number variations of a toxin-encoding plasmid, and (iv) host genomic changes do not match the phenotypic pattern and likely involve selective responses at more than one locus. By exploring the dynamics of coevolution at the phenotypic and genomic level for both host and pathogen simultaneously, our findings demonstrate a more complex model of the Red Queen, consisting of distinct selective processes acting on the two antagonists during rapid and reciprocal coadaptation.