In practical applications, one often has not only one, but several objectives that need to be optimized simultaneously. What is more, modeling such real world problems usually involves using both, continuous and integer variables. This then results in multi-objective mixed-integer optimization problems, which are in focus of this paper. We present an approximation concept, called enclosure, for the nondominated set of such optimization problems and discuss how this concept arises as a natural extension of approximation concepts from single-objective global optimization. Further, we show how to practically compute such an enclosure for multi-objective mixed-integer convex optimization problems using the Hybrid Patch Decomposition algorithm (HyPaD). We demonstrate how exploiting the structure of this kind of optimization problems allows the HyPaD algorithm to operate almost entirely in the criterion space. This is not only in contrast to most algorithms for multi-objective nonconvex optimization problems, but also makes the algorithm’s performance, at least to some extent, independent of the number of optimization variables. Moreover, we exploit the gap between theoretical and practical performance evaluation of solution algorithms, especially with regard to the HyPaD algorithm. More precisely, we present several realizations of the procedures that have originally been treated as black boxes in the theoretical evaluation of the algorithm. Finally, we provide numerical results for selected test instances. More precisely, we evaluate the different realizations of the black box procedures in terms of computation time, provide insights on the influence of the quality parameter chosen for the enclosure, and compare the HyPaD algorithm as a criterion space based method to the MOMIX algorithm as a decision space based method.