In the wake of the Afghan missions, this article assesses the appetite in Australia and New Zealand for an ongoing relationship with NATO. Australia and New Zealand share many commonalities in their cultural, political, and economic profiles. Yet their identities in the realm of defense and security differ subtly, which has important implications for the reception of NATO’s strategic narratives in the Indo-Asia-Pacific region. Drawing on strategic narrative theory (SNT), we assess perceptions of NATO in Australia and New Zealand. By collecting and analyzing empirical data from political, academic, and military elites, we find that there is a keen desire for an on-going partnership with NATO, particularly in maintaining interoperability and in the area of “emerging security challenges.” Although the findings were mostly positive for NATO, New Zealand elites were more reticent about NATO involvement than those in Australia, where elites saw NATO and the Global Partnership as a potentially useful – if under-utilized – asset in areas of non-traditional security cooperation.