Water trading is an effective method for solving regional water shortage problems and addressing the uneven spatiotemporal distribution of water resources. Therefore, taking the Middle Route of China's South-to-North Water Diversion Project (MR-SNWDP) as the research object, we present a study on a feasible water trading scheme in the water-receiving area of Henan Province. First, the tradable water of each calculation unit in the water-receiving area was calculated by analyzing the water-saving potential of different industries. Second, a multi-objective optimization model for trading water between different regions was developed, taking the largest social and economic benefits of the water-receiving area as the objective function. Finally, non-dominated sorting genetic algorithms were used to solve this optimization model, and an optimal scheme for water trading was proposed. The simulated results of the optimal scheme indicate that the total water shortage of the water-receiving areas will decrease by 650.69 million m3, and there will be a surplus of 14.98 million m3 of water, and the gross national product will increase by RMB 130.5 billion at a rate of 5.2%. This demonstrates that the water-receiving areas of Henan Province can effectively alleviate local water shortages by trading water without increasing external water supplies.