According to the increasing worldwide attention to energy and the environmental performance of the building sector, building energy demand should be minimized by considering all energy uses. In this regard, the development of building components characterized by proper values of thermal transmittance, thermal capacity, and radiative properties is a key strategy to reduce the annual energy need for the microclimatic control. However, the design of the thermal characteristics of the building envelope is an arduous task, especially in temperate climates where the energy demands for space heating and cooling are balanced. This study presents a novel methodology for optimizing the thermo-physical properties of the building envelope and its coatings, in terms of thermal resistance, capacity, and radiative characteristics of exposed surfaces. A multi-objective approach is adopted in order to optimize energy performance and thermal comfort. The optimization problem is solved by means of a Genetic Algorithm implemented in MATLAB®, which is coupled with EnergyPlus for performing dynamic energy simulations. For demonstration, the methodology is applied to a residential building for two different Mediterranean climates: Naples and Istanbul. The results show that for Naples, because of the higher incidence of cooling demand, cool external coatings imply significant energy savings, whereas the insulation of walls should be high but not excessive (no more than 13–14 cm). The importance of high-reflective coating is clear also in colder Mediterranean climates, like Istanbul, although the optimal thicknesses of thermal insulation are higher (around 16–18 cm). In both climates, the thermal envelope should have a significant mass, obtainable by adopting dense and/or thick masonry layers. Globally, a careful design of the thermal envelope is always necessary in order to achieve high-efficiency buildings.