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. However, looming obstacles may well interfer with NATO's efforts to enhance relations with the region. Geostrategic realities are not in NATO’s favor: it is a region of crisis; suspicious of the West in general; riddled with internal instability; and is a difficult to build ties with. This monograph examines the existing relationships as well as the remaining obstacles, and proposes solutions to the latter.