Evolutionary costs of parasite resistance arise if genes conferring resistance reduce fitness in the absence of parasites. Thus, parasite-mediated selection may lead to increased resistance and a correlated decrease in fitness, whereas relaxed parasite-mediated selection may lead to reverse evolution of increased fitness and a correlated decrease in resistance. We tested this idea in experimental populations of the protozoan Paramecium caudatum and the parasitic bacterium Holospora undulata. After 8 years, resistance to infection and asexual reproduction were compared among paramecia from (i) infected populations, (ii) uninfected naive populations and (iii) previously infected, parasite-free (recovered) populations. Paramecia from infected populations were more resistant (+12%), but had lower reproduction (-15%) than naive paramecia, indicating an evolutionary trade-off between resistance and fitness. Recovered populations showed similar reproduction to naive populations; however, resistance of recently (<3 years) recovered populations was similar to paramecia from infected populations, while longer (>3 years) recovered populations were as susceptible as naive populations. This suggests a weak, convex trade-off between resistance and fitness, allowing recovery of fitness, without complete loss of resistance, favouring the maintenance of a generalist strategy of intermediate fitness and resistance. Our results indicate that (co)evolution with parasites can leave a genetic signature in disease-free populations.