Driven by the concept of agricultural sustainable development, crop planting structure optimization (CPSO) has become an effective measure to reduce regional crop water demand, ensure food security, and protect the environment. However, traditional optimization of crop planting structures often ignores the impact on regional food supply-demand relations and interprovincial food trading. Therefore, using a system analysis concept and taking virtual water output as the connecting point, this study proposes a theoretical CPSO framework based on a multi-aspect and full-scale evaluation index system. To this end, a water footprint (WF) simulation module denoted as soil and water assessment tool-water footprint (SWAT-WF) is constructed to simulate the amount and components of regional crop WFs. A multi-objective spatial CPSO model with the objectives of maximizing the regional economic water productivity (EWP), minimizing the blue water dependency (BWF_rate), and minimizing the grey water footprint (GWF_grey) is established to achieve an optimal planting layout. Considering various benefits, a full-scale evaluation index system based on region, province, and country scales is constructed. Through an entropy weight technique for order preference by similarity to an ideal solution (TOPSIS) comprehensive evaluation model, the optimal plan is selected from a variety of CPSO plans. The proposed framework is then verified through a case study of the upper-middle reaches of the Heihe River Basin in Gansu province, China. By combining the theory of virtual water trading with system analysis, the optimal planting structure is found. While sacrificing reasonable regional economic benefits, the optimization of the planting structure significantly improves the regional water resource benefits and ecological benefits at different scales.