We propose a multi-objective machine learning approach guaranteed to find the Pareto optimal set of hybrid classification models consisting of comprehensible and incomprehensible submodels. The algorithm run-times are below 1 s for typical applications despite the exponential worst-case time complexity. The user chooses the model with the best comprehensibility-accuracy trade-off from the Pareto front which enables a well informed decision or repeats finding new Pareto fronts with modified seeds. For a classification trees as the comprehensible seed, the hybrids include single black-box model, invoked in hybrid leaves. The comprehensibility of such hybrid classifiers is measured with the proportion of examples classified by the regular leaves. We propose one simple and one computationally efficient algorithm for finding the Pareto optimal hybrid trees, starting from an initial classification tree and a black-box classifier. We evaluate the proposed algorithms empirically, comparing them to the baseline solution set, showing that they often provide valuable improvements. Furthermore, we show that the efficient algorithm outperforms the NSGA-II algorithm in terms of quality of the result set and efficiency (for this optimisation problem). Finally we show that the algorithm returns hybrid classifiers that reflect the expert's knowledge on activity recognition problem well.