Many potentially mutualistic interactions are conditional, with selection that varies between mutualism and antagonism over space and time. We develop a genetic model of temporally variable coevolution that incorporates stochastic fluctuations between mutualism and antagonism. We use this model to determine conditions necessary for the coevolution of matching traits between a host and a conditional mutualist. Using an analytical approximation, we show that matching traits will coevolve when the geometric mean interaction is mutualistic. When this condition does not hold, polymorphism and trait mismatching are maintained, and coevolutionary cycles may result. Numerical simulations verify this prediction and suggest that it remains robust in the presence of temporal autocorrelation. These results are compared with those from spatial models with unrestricted movement. The comparisons demonstrate that gene flow is unnecessary for generating empirical patterns predicted by the geographic mosaic theory of coevolution.