Shape optimization of a rectangular channel with the opposite walls roughened by staggered arrays of dimples has been performed not only to enhance turbulent heat transfer but also to reduce friction loss. The dimpled channel shape is defined by three geometric design variables, and the design points within design space are selected using Latin hypercube sampling. The shape of the channel is optimized with three-dimensional (3-D) Reynolds-averaged Navier-Stokes analysis and surrogate approximation methods. A weighted-sum method for multi-objective optimization is applied to integrate multiple objectives related to heat transfer and friction loss into a single objective. A weighted-average surrogate model is employed for this optimization. By the optimization, the objective function value is improved largely and heat transfer rate is increased much higher than pressure loss increase due to shape deformation. The optimum design results in lower channel height, wider dimple spacing, and deeper dimple. The flow mechanism shows the heat transfer rate is increased mainly in the rear portion of the dimple.