Increasing water scarcity has posed a major constraint to sustain food production in many parts of the world. To study the situation at the regional level, we took Iran as an example and analyzed how an intra-country "virtual water trade strategy" (VWTS) may help improve cereal production as well as alleviate the water scarcity problem. This strategy calls, in part, for the adjustment of the structure of cropping pattern (ASCP) and interregional food trade where crop yield and crop water productivity as well as local economic and social conditions are taken into account. We constructed a systematic framework to assess ASCP at the provincial level under various driving forces and constraints. A mixed-integer, multi-objective, linear optimization model was developed and solved by linear programming. Data from 1990–2004 were used to account for yearly fluctuations of water availability and food production. Five scenarios were designed aimed at maximizing the national cereal production while meeting certain levels of wheat self-sufficiency under various water and land constraints in individual provinces. The results show that under the baseline scenario, which assumes a continuation of the existing water use and food policy at the national level, some ASCP scenarios could produce more wheat with less water. Based on different scenarios in ASCP, we calculated that 31% to 100% of the total wheat shortage in the deficit provinces could be supplied by the wheat surplus provinces. As a result, wheat deficit provinces would receive 3.5 billion m3 to 5.5 billion m3 of virtual water by importing wheat from surplus provinces.