High-strength die steel is widely used for cutting, stamping and molding because of its advantages of high hardness, high toughness and abrasion resistance. However, its efficiency in cutting has always been difficult. In a complex machining process, the optimization of cutting parameters has a significant influence on the stability and quality of products. In this study, an orthogonal experiment of NAK80 for milling is carried out with cutting speed, feed rate and depth of cut, all of which are considered as relevant variables. According to the experimental results, statistical models for cutting force and surface roughness are built using a regression method as objective functions. Superadded the theoretical formula of material removal rate, a multi-objective evolutionary algorithm based on decomposition is used to optimize the cutting parameters and a Pareto solution set is obtained finally.