Determining size and structure of a company’s workforce is one of the most challenging tasks in human resource planning, especially when considering a long-term planning horizon with varying demand. In this paper an approach for integrated staffing and scheduling in a strategic long-term context is presented by applying evolutionary bilevel optimization. For demonstration, the example of determining the number of employees in different categories over the period of one year in a midsized call center of a utility is used. In doing so, two contrary objectives were optimized simultaneously: reduce the overall workforce costs and retain a high scheduling quality. The results show that the proposed approach could be used to support corporate decision making related to strategic workforce planning, not only for call centers but for any other kind of workforce planning involving personnel scheduling.