Staffing rules are an essential management tool in service industries for meeting target service levels. The square-root safety rule, based on the Poisson arrival assumption, has been commonly used. However, empirical findings suggest that arrivals often exhibit `over-dispersion’, meaning that the variance exceeds the mean. In this paper, we develop a new doubly stochastic Poisson process model that captures two key features of over-dispersed arrivals: (i) Taylor’s law, which links the variance to the mean through a power-law relationship, and (ii) temporal correlation decay, where the correlation between arrival counts in disjoint time intervals decreases as the time gap grows. Using this model, we study how over-dispersion affects staffing and derive a closed-form staffing formula to ensure a desired service level. Our formula shows that the safety level grows as a power of the nominal load. The exponent lies between 1/2 (the square-root safety rule) and 1 (the linear safety rule). It depends on the degree of over-dispersion, and it implies that Taylor’s law is the dominant factor in determining staffing levels in heavy traffic. Extensive numerical experiments with both simulated and real arrival data show that our model and staffing rules significantly outperform various alternatives.