Abstract Mutualistic interactions among species are common in most ecosystems. Despite the ubiquitous presence of mutualism, its evolutionary origin and stability has remained enigmatic. Here, we study this problem by generalizing Doebeli and Knowlton's spatial model for the evolution of mutualism [Doebeli, M., Knowlton, N., 1998. The evolution of interspecific mutualism. Proc. Natl. Acad. Sci. USA 95, 8676–8680]. We show that spatial environmental heterogeneity facilitates the evolution of mutualistic interactions under a wide range of plausible conditions. Our model exhibits complex spatial patch dynamics, with environmental heterogeneity reducing among patch migration and leading to increased phenotypic diversity. Moreover, under such environmental heterogeneity, we also observe that both mutualism and exploitative interactions can be permanently present in the same population.