Micro-turbines are promising high power-density engines for distributed generation. In this paper, an optimization process is proposed to design a Swiss-roll type recuperator used to recover the exhaust heat of a micro gas turbine. The recuperator is a counter-flow spiral plate heat exchanger, composed of two flat plates wrapped around each other. There are several design parameters to be optimized, including the number of turns, channel width, plate thickness, and mass flow rate. The complex interconnections of these design parameters make it difficult to analyze the process and select adequate parameter combination to build a recuperator with the highest effectiveness and lowest pressure drop. In order to reduce the number of numerical analysis in the optimization process, a neural network is employed as surrogate model, and a multi-objective DIRECT (DIviding RECTangle) algorithm, named as MO-DIRECT, is developed. After merely 5 iterations, with 3 representative sets selected from the Pareto front for convergence test during each iteration, we were able to find a min-max solution with prediction error lower than 4%. Also, only 24 numerical simulations are required to achieve the results, and only 2,313 steps were conducted in the MO-DIRECT search, rather than 35,343 required in an exhaustive search.