Evolutionary Rescue (ER) occurs when populations, which have declined due to rapid environmental change, recover through genetic adaptation. The success of this process and the evolutionary trajectory of the population strongly depend on the rate of environmental change. Here we investigated how different rates of temperature increase (from 23°C to 32°C) affect population persistence and evolutionary change in experimental microcosms of the protozoan Paramecium caudatum. Consistent with theory on ER, we found that those populations experiencing the slowest rate of temperature increase were the least likely to become extinct and tended to be the best adapted to the new temperature environment. All high-temperature populations were more tolerant to severe heat stress (35°C, 37°C), indicating a common mechanism of heat protection. High-temperature populations also had superior growth rates at optimum temperatures, leading to the absence of a pattern of local adaptation to control (23°C) and high-temperature (32°C) environments. However, high-temperature populations had reduced growth at low temperatures (5-9°C), causing a shift in the temperature niche. In part, the observed evolutionary change can be explained by selection from standing variation. Using mitochondrial markers, we found complete divergence between control and high-temperature populations in the frequencies of six initial founder genotypes. Our results confirm basic predictions of ER and illustrate how adaptation to an extreme local environment can produce positive as well as negative correlated responses to selection over the entire range of the ecological niche.