This paper analyzes the evolution characteristics of the international natural gas trade structure and the integration of the international natural gas market by using complex network theory. It is found that both the LNG and pipeline gas import and export trade networks display scale-free distributions, while the countries in the LNG trade network are linked more closely than those in the pipeline gas trade network. The markets in North America, Europe and Asia are not integrated, which indicates that a unified global natural gas market has not yet been formed. However, the degree of integration between the European and Asian markets is relative strong during 2000–2011. Finally, the integration among international natural gas markets and the inter-regional LNG trades are highly interrelated and mutually influencing.