Antagonistic interactions between hosts and parasites are a key structuring force in natural populations, driving coevolution. However, direct empirical evidence of long-term host-parasite coevolution, in particular 'Red Queen' dynamics--in which antagonistic biotic interactions such as host-parasite interactions can lead to reciprocal evolutionary dynamics--is rare, and current data, although consistent with theories of antagonistic coevolution, do not reveal the temporal dynamics of the process. Dormant stages of both the water flea Daphnia and its microparasites are conserved in lake sediments, providing an archive of past gene pools. Here we use this fact to reconstruct rapid coevolutionary dynamics in a natural setting and show that the parasite rapidly adapts to its host over a period of only a few years. A coevolutionary model based on negative frequency-dependent selection, and designed to mimic essential aspects of our host-parasite system, corroborated these experimental results. In line with the idea of continuing host-parasite coevolution, temporal variation in parasite infectivity changed little over time. In contrast, from the moment the parasite was first found in the sediments, we observed a steady increase in virulence over time, associated with higher fitness of the parasite.