Variation in patient census can complicate nurse staffing, especially when schedules must be posted several weeks in advance and significant random arrivals and lengths of stay exist. While many forecasting models have been developed to predict future census, typically how best to adjust staff levels is left to experience and intuition. Given a thirty-day bed demand forecast, a stochastic decision making approach was developed for adaptive staffing that meets specified nurse-to-patient ratios at minimal total costs--including base staffing, advance adaptations, and same day call-in penalties--which then is optimized via search techniques. Application to a representative 28-bed critical care unit produces a $531,190 (26%) annual savings over current practice. Sensitivity analyses across a range of cost structures, base staffing levels, clinical unit sizes, and patient arrival predictability suggest savings between 16%-31%, which for a mid-size unit can translate to $400,000-$600,000 annually. The optimal policy typically reduces initial base staff levels by 27% on average (range: 14%-60%) and makes greater use of short-term adaptive up-staffing (by 17%-28%). The optimized base staffing level is the most significant factor affecting percent savings, with greater savings when patient arrivals are more predictable but with negligible impact from different clinical unit sizes and number of cost change points. Implications on workforce management, contracts, and care continuity also are discussed.