This article analyzes the features of NATO’s public diplomacy in Central Asia. Based on the neoliberal concept of soft power, the authors expand public diplomacy’s actorness domain, considering its manifestations in the activities of international organizations. The NATO case shows how international organizations can use resources of public diplomacy to legitimize their existence in the changing realities of world politics, to popularize their charter goals and their mission in the international arena, and to garner support for their policies. To this end, NATO not only brings into use a wide range of mechanisms of traditional public diplomacy (print production, scientific and educational exchanges, television), but also actively works in the virtual field (video hosting services, social networks). These areas of the Alliance’s relevant work also cover the post-Soviet Central Asia, which is considered a strategically important region for Russia’s interests. This moment determines the predominantly public-diplomatic nature of NATO’s package of cooperation offered to the countries of the region. Firstly, the military-political relations of Russia with Central Asian states do not leave significant space for NATO’s “hard-power” presence in the region. Secondly, existing opinion polls in some Central Asian countries show negative attitude towards NATO, which requires from the latter to boost its soft power activities. The authors highlight three areas of the Alliance’s core work in the region: information work, scientific and educational work, and expert diplomacy. These mechanisms of public diplomacy not only work on such tactical tasks as raising awareness about the Organization and promoting narrative about the benefits of partnering with it, but also pursue strategic goals—forming loyal circles through interaction with civil society, public opinion leaders, and through training of military personnel, engaging with young generation in the countries of the region. A simplified SWOT analysis the authors conducted shows that despite the attractiveness of NATO’s public diplomacy projects for segments of the region’s population, a number of factors limit its activities. The authors found that, according to the degree of intensity and multidimensionality, NATO’s public diplomacy in Central Asia varies from the most active in Kazakhstan to the least in Turkmenistan. The authors come to the conclusion that, in the face of current strained Russia–NATO relations, formats of public diplomatic work are becoming the most preferable and least sensitive aspect of maintaining the Alliance’s presence in Central Asia.