Human-AI teams have a pervasive impact in various fields including healthcare diagnosis, robotics in manufacturing, cyber-security, autonomous vehicles, and many more. The effectiveness of Human-AI teams highly depends on the set of humans that interact with the AI model for determining the final output. In this paper, we tackle the practical setting where taking the human input is of considerable cost and even expert humans can make mistakes. This paper proposes Probabilistic Labeler Assisted Cost Optimization (PLACO), a two-step framework to find cost-effective subsets of humans for multi-way classification tasks. The inputs from the subset of humans are then combined with the AI model’s output resulting in the most accurate output. For cost-effective human selection given an input task, we estimate human labels by maximizing the posterior probability of a true human label given the AI model’s output on the task. We further derive a value function that determines the value of a given human subset to maximize the lower bound on the overall accuracy of the Human-AI team. We present the theoretical foundations of our human label estimation method and human subset value function. We also empirically demonstrate the effectiveness of PLACO in terms of the Human-AI team’s performance and cost-effectiveness against state-of-art methods on the CIFAR-10H and Imagenet-16H datasets having human annotations.