Mongolia and the Republic of Korea are in the same “partnership basket” for NATO in the Asia-Pacific. The two countries have burgeoning relations with NATO, which represent a relatively new dimension of international engagement for the region. Through the lens of Strategic Narrative Theory, we attempt to grasp how the strategic narratives of the two countries resonate with NATO-originated messages sent to partners in the Asia-Pacific. Both countries are attempting to reach a certain level of stability in terms of their respective geo-strategic positions in the Asia-Pacific. In the context of its “Third Neighbor” approach, Mongolia is applying a hedging strategy with regard to NATO and other actors in the region, including China, Japan, Russia, and the US. Korea assigns primary significance to its bilateral relationships with bigger powers, most obviously and predominantly the US, while considering NATO a broadly useful if sometimes perfunctory additional partner on a number of other security issues.