NATO has gone through a change of strategies in the post Cold War era. It has transformed from a merely military alliance to an active player in the international system confronting a variety of soft and hard threats. NATO's strategies within Europe have proved more successful than its manifested strategies with the Southern Mediterranean countries through the Mediterranean Dialogue and with the Gulf through the Istanbul Cooperative Initiative. There has been minor success on the political and practical level of both initiatives. Both initiatives have taken place on a bilateral level, but they proved to lack momentum. In fact, there are several obstacles hindering further cooperation between NATO and the Southern Mediterranean and the Gulf Arab countries that require mutual efforts and understanding to overcome.