Nations trapped in historical baggage limit their options of growth and stability. Pakistan had been remained trapped into two regional and ideological alliances, expecting for betterment of the region and Muslim Ummah. However, after three decades of its inception, South Asian Association for Regional Cooperation (SAARC) is paralyzed due to Indian hegemonic behaviour and Organization of Islamic Cooperation (OIC) is still plagued with Saudi-Iran rivalry. The two organizations had limited Pakistan’s options of cooperation and growth with other military, economic political and regional alliances. However, there is a new dawn of alliances and bilateral relationship is emerging at Pakistan’s foreign policy horizon. In past few years, Pakistan’s search for new horizons of economic and security cooperation with other regional alliances apart from SAARC and OIC has led Pakistan to a new era of strategic importance with unlimited choices and benefits. Rejuvenating relations with resurging Russia, revamping relations with Iran, entering into Chinese One Belt One Road (OBOR) initiative, repudiating meddling in Yemen/Middle East and entrance into Shanghai Cooperation Organization (SCO) are some major indicators of Pakistan’s foreign policy shift. Efforts to hold upcoming Economic Cooperation Organization (ECO) summit in Islamabad is also string of this new diplomatic pearl. In this backdrop, Pakistan also needs to find new political alliances beyond Indian Ocean. Perhaps extending hand of bilateral cooperation with North Atlantic Treaty Organization (NATO) can serve Pakistan’s interest in national and regional security spheres of the country. NATO and Pakistan have a decade long history of fluctuated relationship. The cooperation emerged in the wake of the US led NATO invasion in Afghanistan. Pakistan and NATO led International Security Assistance Forces (ISAF) found common grounds of bilateral security cooperation along Pakistan-Afghanistan border region. In 2005, Deputy Assistant Secretary General of NATO Ambassador Alessandro Minu to Rizzo visited Pakistan. Since Pakistan always viewed NATO with the US prism, hence cooperation between Pakistan and NATO could not develop significantly. Short era of limited cooperation started between Pakistan and NATO after latter’s generous response to 2005 devastating earthquake. NATO had launched an airlift of urgently needed supplies and deployed its engineers, medical units and specialist equipment to Pakistan. In order to facilitate the relief efforts, NATO had established a massive air-bridge, in addition to utilizing the assets of the NATO Response Force (NRF). During that period, NATO had supplied almost 3500 tons of food and medical supplies. The air-bridge helped shifting over 7600 people to safe places and more than 8000 patients were treated under NATO medical staff. In addition NATO helped Pakistan Army in clearing roads of the affected area. NATO’s generous response reciprocated Pakistan by initiating political dialogue with former in 2006. The initiative of political response helped starting military training courses for Pakistani military officers and establishment of high level military and political contacts between the two. A milestone of cooperation was achieved in 2007, when Pakistan and NATO had established Joint Intelligence Operations Centre (JIOC) at ISAF Head Quarters in Kabul. The center has facilitated for numerous intelligence operations along Pakistan-Afghanistan border region against terrorists. However, the incremental cooperation between the two dented due to NATO’s attack on Salala check post killing 24 soldiers of Pakistan Army. In result, Pakistan closed ground communication lines for ISAF transit, which increased cost of NATO’s stay in Afghanistan. NATO’s draw down from Afghanistan and Pakistan’s efforts for Afghan national reconciliation has increased former’s importance in the region. The work of the Tripartite Commission, a joint forum on military and security issues that brings together representatives from the NATO-led ISAF, Afghanistan and Pakistan, reflects the importance of NATO-Pakistan military-to-military cooperation in the context of Afghanistan. Pakistan and NATO have common objective of countering-terrorism with different approaches, which restrained both to enter into a deeper and broader cooperation on issues such as security and stability in Afghanistan, anti-narcotics campaign along Pakistan-Afghanistan border region and repatriation of Afghan refugees. Intelligence sharing, border security, countering improvised explosive devices (IEDs) along the Pakistan-Afghanistan border region, narcotics smuggling are offering prospects of bilateral cooperation. By establishing deeper, wider and effective cooperation with NATO, Pakistan can also dismantle Tehreek-i-Taliban Pakistan (TTP) safe havens in Afghanistan. In this glaring era of Pakistan’s flexible approach to regional and international situation, deeper and wider cooperation with NATO is inexorable, which will not only serve Pakistan’s interests of national security but also will help establishing stability in Afghanistan. The writer works for IPRI, a think tank based in Islamabad