We consider the anesthesiologist staff planning problem for operating services departments in large multi-specialty hospitals. In this problem, the planner makes monthly and daily decisions to minimize total costs. The monthly decisions include deciding how many anesthesiologists should be on regular duty and how many should be on-call for each day of the month and for each specialty. The daily decisions involve determining how many on-call anesthesiologists to actually use in the surgical schedule for the next day. Total costs comprise of explicit and implicit costs. Explicit costs include the costs of calling an anesthesiologist from call and overtime costs, and are decided by the organization. Implicit costs are the costs of keeping but not calling an anesthesiologist on-call and under-utilizing an anesthesiologist, and these have to be deduced from past decisions. The staff planning problem is important in operating services departments. This paper solves this problem by incorporating implicit costs, demand uncertainty and service specialties. This is unique both in practice and the academic literature. We model the staff planning problem as a two-stage integer stochastic dynamic program. We develop structural properties of this model and use them in a sample average approximation algorithm constructed to solve this problem. We develop a procedure to estimate the implicit costs, which are included in this model. Using data from the operating services department at the UCLA Ronald Reagan Medical Center, we and that the cost of not calling an anesthesiologist on the on-call list is 56% more than the cost of actually calling the anesthesiologists. Also, the cost of idle time for anesthesiologists was 94% more than the cost of overtime. Our model shows the potential to reduce overall costs by 13%. We provide managerial insights related to hiring decisions by specialty, sensitivity to cost parameters, and improvements in prediction of booked time durations.