Abstract: Many theoretical models of evolution assume that all competing individuals experience the same environment. Here, we consider the more realistic scenario of evolution in heterogeneous environments. We introduce a novel formalism to approach any form of spatial fitness heterogeneity in an evolutionary graph. We calculate the condition for natural selection to favor the mutant type relative to the resident on a complete graph structure. Environmental heterogeneity elucidates an interesting asymmetry between the mutant and resident types. Mutant heterogeneity suppresses fixation probability, and if strong enough, it can completely offset the effects of natural selection. In contrast, resident heterogeneity can amplify a mutant’s fixation probability if population is small and has no effect on mutant fixation probability otherwise. Our results hold for any environmental heterogeneity and selection intensity. We address generalization of the above observations to other graph structures, as well as heterogeneous evolutionary games.