Many queueing systems with time-dependent arrivals require time-dependent staffing to provide satisfactory service levels at reasonable cost. Feldman et al. (Manag Sci 54(2):324–338, 2008) proposed an iterative staffing algorithm designed to deliver time-stable performance in which successive iterations were evaluated via simulation experiments. In this paper we present and evaluate an analytical queueing model combined with an iterative staffing algorithm to be used for setting staffing levels to achieve time-stable performance in call centre type queues. Empirical results show that the method to be considerably faster than simulation based methods and considerably more accurate than the industry standard analytical methods.