Molecular evolution is a stochastic process governed by fitness, mutations, and reproductive fluctuations in a population. Here, we study evolution where fitness itself is stochastic, with random switches in the direction of selection at individual genomic loci. As the correlation time of these fluctuations becomes larger than the diffusion time of mutations within the population, fitness changes from an annealed to a quenched random variable. We show that the rate of evolution has its maximum in the crossover regime, where both time scales are comparable. Adaptive evolution emerges in the quenched fitness regime (evidence for such fitness fluctuations has recently been found in genomic data). The joint statistical theory of reproductive and fitness fluctuations establishes a conceptual connection between evolutionary genetics and statistical physics of disordered systems.