In this study, we constructed a new algorithm to determine the optimal parameters for friction stir welding including rotational speed, welding speed, axial force, tool pin profile, and tool material. The objective of welding is to maximize the ultimate tensile strength of the welded aluminum. The proposed method combines the response surface method and the modified differential evolution algorithm (RSM-MDE). RSM-MDE is a method that involves both experimental and simulation procedures. It is composed of four steps: (1) finding the number of parameters and their levels that affect the efficiency of the friction stir welding, (2) using RSM to formulate the regression model, (3) using the MDE algorithm to find the optimal parameter of the regression model obtained from (2), and (4) verifying the results obtained from step (3). The optimal parameters generated by the RSM-MDE method were a rotation speed of 1417.68 rpm, a welding speed of 60.21 mm/min, an axial force of 8.44 kN, a hexagon-tapered tool pin profile, and the SKD 11 tool material. The ultimate tensile strength obtained from this set of parameters was 294.84 MPa, which was better than that of the RSM by 1.48%.