Exploring the capability of organisms to cope with human-caused environmental change is crucial for assessing the risk of extinction and biodiversity loss. We study the consequences of changing nutrient pollution for the freshwater keystone grazer, Daphnia, in a large lake with a well-documented history of eutrophication and oligotrophication. Experiments using decades-old genotypes resurrected from the sediment egg bank revealed that nutrient enrichment in the middle of the 20th century, resulting in the proliferation of harmful cyanobacteria, led to the rapid evolution of grazer resistance to cyanobacteria. We show here that the subsequent reduction in nutrient input, accompanied by a decrease in cyanobacteria, resulted in the re-emergence of highly susceptible Daphnia genotypes. Expression and subsequent loss of grazer resistance occurred at high evolutionary rates, suggesting opposing selection and that maintaining resistance was costly. We provide a rare example of reversed evolution of a fitness-relevant trait in response to relaxed selection.