Fuel design is a complex multi-objective optimization problem in which facile and robust methods are urgently demanded. Herein, a complete workflow for designing a fuel blending scheme is presented, which is theoretically supported, efficient, and reliable. Based on the data distribution of the composition and properties of the blending fuels, a model of polynomial regression with appropriate hypothesis space was established. The parameters of the model were further optimized by different intelligence algorithms to achieve high-precision regression. Then, the design of a blending fuel was described as a multi-objective optimization problem, which was solved using a Nelder–Mead algorithm based on the concept of Pareto domination. Finally, the design of a target fuel was fully validated by experiments. This study provides new avenues for designing various blending fuels to meet the needs of next-generation engines.