A reduction in the strength of selection is expected to cause the evolution of reduced trait expression. Elimination of a parasite should thus cause the evolution of reduced resistance to that parasite. To test this prediction in nature, we studied the fourth- and eighth-generation descendants of guppies ( Poecilia reticulata ) introduced into four natural streams following experimental elimination of a common and deleterious parasite ( Gyrodactylus spp.). After two generations of laboratory rearing to control for plasticity and maternal effects, we infected individual fish to assess their resistance to the parasite. Contrary to theoretical expectations, the introduced guppy populations had rapidly and repeatably evolved increased resistance to the now-absent parasite. This evolution was not owing to a resistance-tolerance trade-off, nor to differences in productivity among the sites. Instead, a leading candidate hypothesis is that the rapid life-history evolution typical in such introductions pleiotropically increases parasite resistance. Our study adds a new dimension to the growing evidence for contemporary evolution in the wild, and also points to the need for a re-consideration of simple expectations from host–parasite theory. In particular, our results highlight the need for increased consideration of multiple sources of selection and pleiotropy when studying evolution in natural contexts.