A computationally-efficient procedure for multi-objective design of antennas is presented. Our approach is general; however, in the particular case study considered here, the goal is to improve the antenna gain while ensuring that the matching requirements are satisfied. Our approach exploits the multi-objective evolutionary algorithm (MOEA) working with a fast surrogate model of the antenna obtained with kriging interpolation of coarse-discretization electromagnetic (EM) simulation data. To reduce the computational cost of setting up the kriging model, the antenna structure is decomposed into the antenna itself and the matching structure, with separate models constructed for both parts. Response correction techniques are subsequently applied to refine the designs obtained by MOEA. Our methodology allows us to obtain—at a low computational cost—a set of designs corresponding to various trade-offs between antenna gain and the refection coefficient.