The alumina evaporation process (AEP) is an indispensable step for the reuse of sodium aluminate solution by evaporating excess water contained in the solution. The selection of optimal operating parameters is a complicated task because the process is influenced by many nonlinear factors when both the quality and quantity of the product are concerned. In this paper, we formulate a multi-objective optimization model to maintain the balance of operating costs and energy efficiency in AEP, and a multi-objective state transition algorithm (MOSTA) is proposed for solving this problem. With the aim of solving the constrained multi-objective problem, a search archive strategy of elite populations and a novel infeasible solution replacement mechanism are integrated into STA. Some infeasible solutions with better performances are allowed to be saved and participate randomly in the evolution to select optimal solutions from all possible directions. A mutation operator is introduced into the evolutionary process to enhance the global search ability. Simulation results from some benchmark test problems show that the proposed method tends to converge quickly and effectively to the true Pareto frontier with better distribution. The proposed algorithm is successfully applied to solve the multi-objective optimization problem arising in AEP. The optimal results show that operating costs and energy loss are considerably reduced, by approximately 13.63% and 13.39%, respectively.