Given a micro pin-fin array cooling scheme with these constraints: (a) given maximum allowable temperature of thematerial (the hot spot temperature), (b) given inlet cooling fluid temperature, (c) given total pressure loss (pumping power affordable), and (d) given overall thickness of the entire micro pinfin cooling array, find the maximum possible average heat flux on the hot surface and find the maximumpossible heat flux at the hot spot under the condition that the entire amount of the inputted heat is removed by the cooling fluid. The goal was to create an optimum performance map for a cooling micro array having specified inlet coolant temperature and maximum temperature. Fully 3D conjugate heat transfer analysis was performed on each of the randomly created candidate configurations. Response surfaces based on Radial Basis Functions were coupled with a genetic algorithm to arrive at a Pareto set of best trade-off solutions. These Pareto optimized configurations indicate themaximum physically possible heat fluxes for specifiedmaterial and constraints. Detailed off-design performance maps of such Pareto-optimized cooling arrays of micro pin-fins were calculated that demonstrate superior on-design and off-design performance of pin-fins having symmetric convex cross sections as opposed to the commonly used circular cross sections.