Many mutualistic interactions are probably not mutualistic across all populations and years. This article explores consequences of this observation with a series of genetic models that consider how variable mutualisms coevolve. The first models, previously introduced in a general coevolutionary context, consider two coevolving species whose fitness interactions change between beneficial and antagonistic in response to independent spatial or temporal variation in the abiotic or biotic environment. The results demonstrate that both temporal and spatial variability in fitness interactions can cause partner species with tightly matched traits favored by unconditional mutualisms to be vulnerable to evolutionary invasion by alternative types. A new model presented here shows that an additional mutualistic species can have a similar effect and can even cause fitness interactions between the other two species to evolve. Under some conditions, the pairwise interactions can change unidirectionally from mutualistic to antagonistic, with virtually no evolutionary change in either partner species. In other cases, fitness interactions between the species pair can oscillate between mutualism and antagonism as a result of coevolution in the third species. Taken as a whole, these theoretical results suggest that many features of mutualistic coevolution can best be understood by considering spatial, temporal, and community-dependent patterns of fitness interactions.