While NATO was created with a primary outlook to the East, its Southern rim was neglected strategically until the end of the Cold War. Since then, the Alliance has undertaken a number of efforts to build strategic relationships with the Middle East and North Africa, recognizing the region's importance for Allied security. But obstacles are on the way to deepened relations, and geostrategic realities do not play in NATO's favor: a region of crisis, suspicious of the West in general and riddled with internal instability, is a difficult one to build ties with. This monograph examines the existing relationships as well as the remaining obstacles, and proposes solutions to the latter.