In order to further promote the trade development of western China towards the “Belt and Road”, identify the countries for building international logistics hub, and construct the cross-border logistics hub network of western China along the “Belt and Road” are urgently needed. This paper proposes a two-stage method to study the construction of cross-border logistics hub network. In the first stage, 27 nations are initially selected using the fuzzy C-means clustering approach. These 27 nations enjoy better trading conditions and higher trade volumes with China than other the “Belt and Road” cooperation nations. In the second stage, this paper puts forward the maximum criterion of logistics gravity based on the gravity model, and objectively determines 14 countries for building international logistics hub. These nations, which include China, Russia, the United Arab Emirates, and others, have a high degree of international logistics development and robust logistics interconnection. According to the logistics connecting countries of these 14 countries, the logistics circle is divided. This paper connects China with other hub countries in the logistics circle, then the cross-border logistics hub network is constructed.