We present a novel conceptual framework and methodology for studying virtual water trade. We utilize complex network theory to analyze the structure of the global virtual water trade associated with the international food trade. In the global virtual water trade network, the nations that participate in the international food trade correspond to the nodes, and the links represent the flows of virtual water associated with the trade of food from the country of export to the country of import. We find that the number of trade connections follows an exponential distribution, except for the case of import trade relationships, while the volume of water that each nation trades compares well with a stretched exponential distribution, indicating high heterogeneity of flows between nations. There is a power law relationship between the volume of virtual water traded and the number of trade connections of each nation. Highly connected nations are preferentially linked to poorly connected nations and exhibit low levels of clustering. However, when the volume of virtual water traded is taken into account, this structure breaks down. This indicates a global hierarchy, in which nations that trade large volumes of water are more likely to link to and cluster with other nations that trade large volumes of water, particularly when the direction of trade is considered. Nations that play a critical role in maintaining the global network architecture are highlighted. Our analysis provides the necessary framework for the development of a model of global virtual water trade aimed at applications ranging from network optimization to climate change impact evaluations.