The evolution of cis-regulatory elements (or enhancers) appears to proceed at dramatically different rates in different taxa. Vertebrate enhancers are often very highly conserved in their sequences, and relative positions, across distantly related taxa. In contrast, functionally equivalent enhancers in closely related Drosophila species can differ greatly in their sequences and spatial organization. We present a population-genetic model to explain this difference. The model examines the dynamics of fixation of pairs of individually deleterious, but compensating, mutations. As expected, small populations are predicted to have a high rate of evolution, and the rate decreases with increasing population size. In contrast to previous models, however, this model predicts that the rate of evolution by pairs of compensatory mutations increases dramatically for population sizes above several thousand individuals, to the point of greatly exceeding the neutral rate. Application of this model predicts that species with moderate population sizes will have relatively conserved enhancers, whereas species with larger populations will be expected to evolve their enhancers at much higher rates. We propose that the different degree of conservation seen in vertebrate and Drosophila enhancers may be explained solely by differences in their population sizes and generation times.