The factors underlying the temporal dynamics of rubella outside of Europe and North America are not well known. Here we used 20 years of incidence reports from Mexico to identify variation in seasonal forcing and magnitude of transmission across the country and to explore determinants of inter-annual variability in epidemic magnitude in rubella. We found considerable regional variation in both magnitude of transmission and amplitude of seasonal variation in transmission. Several lines of evidence pointed to stochastic dynamics as an important driver of multi-annual cycles. Since average age of infection increased with the relative importance of stochastic dynamics, this conclusion has implications for the burden of congenital rubella syndrome. We discuss factors underlying regional variation, and implications of the importance of stochasticity for vaccination implementation.