The shortage of nurses has attracted considerable attention due to its direct impact on the quality of patient care. High workloads and undesirable schedules are two major reasons for nurses to report job dissatisfaction. The focus of this article is to find non-dominated solutions to an integrated nurse staffing and assignment problem that minimizes excess workload on nurses and staffing cost. A stochastic integer programming model with an objective to minimize excess workload subject to a hard budget constraint is presented. Three solution approaches are applied, which are Benders decomposition, Lagrangian relaxation with Benders decomposition, and a heuristic based on nested Benders decomposition. The maximum allowable staffing cost in the budget constraint is varied in the Benders decomposition and nested Benders decomposition approaches, and the budget constraint is relaxed and the staffing cost is penalized in the Lagrangian relaxation with Benders decomposition approach. Non-dominated bicriteria solutions are collected from the algorithms. The effectiveness of the model and algorithms is demonstrated in a computational study based on data from two medical-surgical units at a Northeast Texas hospital. A floating nurses policy is also evaluated. Finally, areas of future research are discussed. © 2013 Taylor & Francis Group, LLC.