Host-parasite coevolution can lead to a variety of outcomes, but whereas experimental studies on clonal populations have taken prominence over the last years, experimental studies on obligately out-crossing organisms are virtually absent so far. Therefore, we set up a coevolution experiment using four genetically distinct lines of Tribolium castaneum and its natural obligately killing microsporidian parasite, Nosema whitei. After 13 generations of experimental coevolution, we employed a time-shift experiment infecting hosts from the current generation with parasites from nine different time points in coevolutionary history. Although initially parasite-induced mortality showed synchronized fluctuations across lines, a general decrease over time was observed, potentially reflecting evolution towards optimal levels of virulence or a failure to adapt to coevolving sexual hosts. © 2011 The Authors. Journal of Evolutionary Biology © 2011 European Society For Evolutionary Biology.