There exists large space to save energy of high-sulfur natural gas purification process. The multi-objective optimization problem has been investigated to effectively reduce the total comprehensive energy consumption and further improve the production rate of purified gas. A steady-state simulation model of high-sulfur natural gas purification process has been set up by using ProMax. Seven key operating parameters of the purification process have been determined based on the analysis of comprehensive energy consumption distribution. To solve the problem that the process model does not converge in some conditions, back-propagation (BP) neural network has been applied to substitute the simulation model to predict the relative parameters in the optimization model. The uniform design method and the table U21 (107) have been applied to design the experiment points for training and testing BP model. High prediction accuracy can be achieved by using the BP model. Non-dominated sorting genetic algorithm-II has been developed to optimize the two objectives, and 100 Pareto optimal solutions have been obtained. Three optimal points have been selected and evaluated further. The results demonstrate that the total comprehensive energy consumption is reduced by 13.4% and the production rate of purified gas is improved by 0.2% under the optimized operating conditions.