The evolution of natural organisms is ultimately driven by the invasion and possible fixation of mutant alleles. The invasion process is highly stochastic, however, and the probability of success is generally low, even for advantageous alleles. Additionally, all organisms live in a stochastic environment, which may have a large influence on what alleles are favorable, but also contributes to the uncertainty of the invasion process. We calculate the invasion probability of a beneficial, mutant allele in a monomorphic, large population subject to stochastic environmental fluctuations, taking into account density- and frequency-dependent selection, stochastic population dynamics and temporal autocorrelation of the environment. We treat both discrete and continuous time population dynamics, and allow for overlapping generations in the continuous time case. The results can be generalized to diploid, sexually reproducing organisms embedded in communities of interacting species. We further use these results to derive an extended canonical equation of adaptive dynamics, predicting the rate of evolutionary change of a heritable trait on long evolutionary time scales.