Currently, the state of trust between China and its neighboring countries is not very optimistic. This paper first divides China's peripheral trust problems into three kinds: confrontational trust crises, competitive-cooperative trust challenges and suspective trust perplex. Confrontational trust crisis refers to the situation wherein neighboring countries see China as their major threats or opponents, and take a strong confrontational stances against China. As a result, the trust between China and these countries falls into ″malicious confrontation″ crises. Competitive-cooperative trust challenges refer to certain neighboring countries viewing China as their major competitor or potential competitor, but not to the extent to be antagonistic against China. These states still show their intent to balance or guard against China while cooperating at the same time. This situation brings challenges to their bilateral relationships with China. Suspective trust perplex refers to the phenomenon where some small neighboring countries do not have strategic interests in confronting with or competing against China, however, they are worried about China's influence due to their comprehensive incapabilities.These trust problems indicate that the distrust that neighboring countries feel towards China is mainly based on their traditionally secure relationship with China. From the perspective of ″embedding theory,″such trust problems reflect the ″ undersocialized″ inter-state security relationships, as well as a consequence of disembedding national security from the framework of global security. Thus, this paper brings forward a new perspective of″security embeddedness″for constructing trust on China's periphery. ″Security embeddedness″is a conceptual expansion of″embeddedness″in the international security studies. It mainly argues that a single country's security and security interactions between countries are embedded in social networks formed by inter-state relationships. During the process of security embeddedness, individual security acts will be limited by specific situations within the social network. It can help reduce uncertainty during security interactions and ensure national security by emphasizing relationalism. In fact, national security in the era of globalization can be seen as a kind of complex security which emphasizes nations' ″self-others″ relationship. Inter-state security embeddedness stresses sharing and cogovernance, which provides the possibility of inter-state trust reconstruction. We thus propose three paths for solving China's neighboring trust problems on the perspective of security embeddedness. First, we make use of network structural advantages of the United States during the process of promoting the new model of major-country relationship between China and the United States, and of improving China's network centrality by taking advantage of non-traditional security governance. The second path boosts the institutional national security embeddedness and copes with the co-operational trust challenge by deepening and regulating the interregional security cooperation among regional powers within the institutional framework, thereby releasing goodwill and sincerity of security cooperation to the neighboring countries by strengthening the institutional multilateral security embeddedness. Moreover, China should initiatively take the security responsibility within the framework and attach importance to offering the institutional periphery public products. Last but not least, underlining national security cultural embeddedness in order to solve the suspective trust perplex, promoting the formation of collective identity between China and its neighboring countries by adhering to self-disciplined actions, initiating and forming a partnership centered with equality and respect, and focused on resolving non-traditional security problems.