Genetic interactions among mutations (epistasis) can make adaptation unpredictable, rendering evolutionary trajectories contingent on initial mutations. I use experimental evolution in yeast *Saccharomyces cerevisiae *to understand the structure of epistasis among beneficial mutations and its effects on adaptation. I find that small genetic differences among Founder strains can lead to large differences in their rates of adaptation. However, this variability is not random, but rather the initial fitness of a Founder strongly predicts the rate at which it will adapt. Surprisingly, Founder identity has no detectable influence on which mutations its descendants would acquire. Instead, there is a striking inverse relationship between the effects of mutations and the fitnesses of backgrounds in which they occur. Moreover, such "diminishing returns" epistasis appears to be global, i.e., even apparently functionally unrelated mutations interact strongly, but only through their combined effect on fitness. Thus, while adaptation at the sequence level is highly stochastic, fitness evolution is remarkably predictable because adaptation rate of a strain is determined only by global fitness-mediated epistasis, not by the identity of individual mutations.