Multi-task problems frequently arise in machine learning when there are multiple target variables, which share a common synergy while being sufficiently different that optimizing on any of the task does not necessarily imply an optimum for the others. In this work, we develop PEMBOT, a novel Pareto-based multi-task classification framework using a gradient boosted tree architecture. The proposed methodology involves a) generating multiple instances of Pareto optimal trees, b) diverse subset selection using a determinantal point process (DPP) model, and c) ensembling of diverse Pareto optimal trees to yield the final output. We tested our framework on a problem from an e-commerce domain wherein the task is to predict at order placement time the different adverse scenarios in the order shipment journey such as the package getting lost or damaged during shipment. This model enables us to take preemptive measures to prevent these scenarios from happening resulting in significant operational cost savings. Further, to show the generality of our approach, we demonstrate the performance of our algorithm on a publicly available wine quality prediction dataset and compare against state-of-the-art baselines.