Motivated by diverse application areas such as healthcare, call centers, and crowdsourcing, we consider the design and operation of service systems that process tasks with types that are ex ante unknown, and employ servers with different skill sets. Our benchmark model involves two types of tasks, Easy and Hard, and servers that are either Junior or Senior in their abilities. The service provider determines a resource allocation policy, i.e., how to assign tasks to servers over time, with the goal of maximizing the system’s long-term throughput. Information about a task’s type can only be obtained while serving it. In particular, the more time a Junior server spends on a task without service completion, the higher her belief that the task is Hard and thus needs to be rerouted to a Senior server. This interplay between service time and task-type uncertainty implies that the system’s resource allocation policy and staffing levels implicitly determine how the provider prioritizes between learning and actually serving. We show that the performance loss due to the uncertainty in task types can be significant and, interestingly, that the system’s stability region is largely dependent on the rate at which information about tasks’ types is generated. Furthermore, we consider endogenizing the servers’ capabilities: assuming that training is costly, we explore the problem of jointly optimizing over the training levels of the system’s server pools, the staffing levels, and the resource allocation policy. We find that among optimal designs there always exists one with a “hierarchical” structure, where all tasks are initially routed to the least skilled servers and then progressively move to more skilled ones, if necessary. Comparative statics indicate that uncertainty in task types leads to significantly higher staffing cost and less specialized server pools.