The three main objectives of air-conditioning and heat pump research are to improve energy efficiency, reduce cost and lower environmental impact. Air-to-refrigerant heat exchangers are key component in such systems. A great deal of effort is spent on the design and optimization of these heat exchangers. It has been well known that smaller channel sizes can significantly improve their performance. Recent analyses demonstrate great potential for improvement in terms of size, weight, refrigerant charge and heat transfer by employing tube outer diameters below 2 mm (0.08 in). This paper presents a comprehensive approach for the design optimization of heat exchangers with small hydraulic diameters below 2 mm (0.08 in). The goal of the design optimization is to develop heat exchanger designs that are at least 20% more compact than the current state of the art designs. Empirical correlations for air side performance are not readily available in open literature for tubes with such small hydraulic diameters. Hence, Computational Fluid Dynamics (CFD) -based correlations developed for bare-tube bundle and fin-and-tube, with low find densities, are used. The CFD based models are validated against experimental data before using them for design optimization. Approximated Assisted Optimization (AAO) method, using Multi-Objective Genetic Algorithm (MOGA) is employed to find optimum designs that surpass current state-of-the-art Micro-Channel heat exchangers in size, performance and refrigerant charge. Various designs for air-to-water radiators and air-to-refrigerant condensers are investigated. The investigated geometries have the potential to be at least 20% better than the current state of the art heat exchangers.