The shape optimization of a micro-channel heat sink with a grooved structure has been performed using a multiobjective evolutionary algorithm. The thermal-resistance and pumping-power characteristics of the micro-channel heat sink have been investigated numerically. For optimization, four design variables, i.e., the ratios of the groove depth to the micro-channel height, the groove pitch to the micro-channel height, the groove diameter to pitch, and the micro-channel width to height are selected. The thermal resistance and the pumping power are the objective functions. The Navier-Stokes and energy equations for laminar flow and conjugate heat transfer are solved using a finite-volume solver. In comparison with a smooth micro-channel, a decrease in the thermal resistance and an increase in the Nusselt number are obtained in a grooved micro-channel at the expense of pumping power. The thermal resistance in a grooved micro-channel is lower than that in a smooth micro-channel for a fixed pumping power. The ratio of the groove pitch to micro-channel height is found to be the most Pareto-sensitive (sensitive along the Pareto-optimal front), whereas the ratio of the micro-channel width to height is found to be the least Pareto-sensitive variable.