We study a capacity sizing problem in service systems with uncertain arrival rates telephone call centers are canonical examples of such systems. The objective is to choose a staffing level that minimizes the sum of personnel costs and abandonment/waiting time costs. We formulate a simple fluid analogue, which is in essence a newsvendor problem, and demonstrate that the solution it prescribes performs remarkably well. In particular, the gap between the performance of the optimal staffing level and that of our proposed prescription is independent of the ``size of the system, i.e., it remains bounded as the system size (demand volume) increases. This stands in contrast to the more conventional theory that applies when arrival rates are known, and commonly used rules-of-thumb predicated on it. Specifically, in that setting the difference between the optimal performance and that of the fluid solution diverges at a rate proportional to square-root of the size of the system. One manifestation of this is the celebrated square root safety staffing principle that dates back to work of Erlang, which augments solutions of the deterministic analysis with additional servers of order square root the volume of demand. In our work, we establish that this type of prescription is needed only when arrival rates are suitably ``predictable.