“Divide and conquer” has been a common practice to address complex learning tasks such as multi-view object detection. The positive examples are divided into multiple subcategories for training subcategory classifiers individually. However, the subcategory labeling process, either through manual labeling or through clustering, is suboptimal for the overall classification task. In this paper, we propose multiple category boosting (McBoost), which overcomes the above issue through adaptive labeling. In particular, a winner-take-all McBoost (WTA-McBoost) scheme is presented in detail. Each positive example has a unique subcategory label at any stage of the training process, and the label may switch to a different subcategory if a higher score is achieved by that subcategory classifier. By allowing examples to self-organize themselves in such a winner-take-all manner, WTA-McBoost outperforms traditional schemes significantly, as supported by our experiments on learning a multi-view face detector.