The quality and cost of coke are directly affected by the proportion of different categories of coal, while the coal blending in coking process is a complex one with multiple objectives and constraints. In this study, a multi-objective simulated annealing algorithm (MOSA)-based coal blending optimization approach in coking process is proposed. The objective function which considers the coke quality indexes and its cost for coal blending is constructed, along with the corresponding constraints. Then, a modified MOSA based on the decision space search strategy is presented to calculate the optimal solution, in which the value of the variable in intermediate solution will mutate with a certain probability during the search process, thereby expanding the search range. The validation experiments using actual coal blending data are carried out. The results indicate that the strategy proposed in this paper is capable of searching the Pareto-optimal (PO) solutions accurately and comprehensively, which exhibits better performance than the existing ones, and can provide guidance for coking production.