The objective of this paper is to investigate optimum process parameters and tool geometries in Friction Stir Welding (FSW) to minimize temperature difference between the leading edge of the tool probe and the work piece material in front of the tool shoulder, and simultaneously maximize traverse welding speed, which conflicts with the former objective. An evolutionary multi-objective optimization algorithm (i.e. NSGA-II), is applied to find multiple trade-off solutions followed by a gradient-based local search (i.e. SQP) to improve the convergence of the obtained Pareto-optimal front. In order to reduce the number of function evaluations in the local search procedure, the obtained non-dominated solutions are clustered in the objective space and consequently, a postoptimality study is manually performed to find out some common design principles among those solutions. Finally, two reasonable design choices have been offered based on several process specific performance and cost related criteria.