The present work aims at optimizing the geometry of curved trapezoidal winglets to enhance heat transfer rates (expressed as Colburn factor, j) and minimize pressure losses (expressed as friction factor, f). A fin-and-tube heat exchanger was analyzed with winglets mounted on the alternate tube and on either side of the fins. Multi-objective optimization was performed using the genetic algorithm (GA) to maximize j and minimize f. Two surrogate models, viz. response surface methodology (RSM) and artificial neural network (ANN), were considered as inputs to GA. To reduce the number of runs, a sensitivity analysis was first performed to select the most influential geometrical parameters for optimization. The values of j and f in the design of the experiments table were computed using CFD. The Pareto front points elucidated a significant improvement compared with the reference model along with a broad choice for the designers, not only for the design condition but also for the off-design inlet condition.