No environment is constant over time, and environmental fluctuations impact the outcome of evolutionary dynamics. Survival of a population not adapted to some environmental conditions is threatened unless, for example, a mutation rescues it, an eco-evolutionary process termed evolutionary rescue. We here investigate evolutionary rescue in an environment that fluctuates between a favourable state, in which the population grows, and a harsh state, in which the population declines. We develop a stochastic model that includes both population dynamics and genetics. We derive analytical predictions for the mean extinction time of a non-adapted population given that it is not rescued, the probability of rescue by a mutation, and the mean appearance time of a rescue mutant, which we validate using numerical simulations. We find that stochastic environmental fluctuations, resulting in quasi-periodic environmental changes, accelerate extinction and hinder evolutionary rescue compared with deterministic environmental fluctuations, resulting in periodic environmental changes. We demonstrate that high equilibrium population sizes and per capita growth rates maximize the chances of evolutionary rescue. We show that an imperfectly harsh environment, which does not fully prevent births but makes the death rate to birth rate ratio much greater than unity, has almost the same rescue probability as a perfectly harsh environment, which fully prevents births. Finally, we put our results in the context of antimicrobial resistance and conservation biology.