We address the problem of multi-task learning with no label correspondence among tasks. Learning multiple related tasks simultane- ously, by exploiting their shared knowledge can improve the predictive performance on every task. We develop the multi-task Adaboost en- vironment with Multi-Task Decision Trees as weak classifiers. We first adapt the well known decision tree learning to the multi-task setting. We revise the information gain rule for learning decision trees in the multi- task setting. We use this feature to develop a novel criterion for learning Multi-Task Decision Trees. The criterion guides the tree construction by learning the decision rules from data of different tasks, and representing different degrees of task relatedness. We then modify MT-Adaboost to combine Multi-task Decision Trees as weak learners. We experimentally validate the advantage of the new technique; we report results of ex- periments conducted on several multi-task datasets, including the Enron email set and Spam Filtering collection.