Seas and deserts are uniting and dividing elements of human life on this planet. The Mediterranean region, North Africa, and the Sahel have witnessed a long history of historical cycles of cooperation and conflict. Since the Arab Spring and the fall of Qaddafi in Libya in 2011, the region has received increasing international attention given the combination of violent conflict and unprecedented migration flows at Europe’s doorstep. This paper aims to analyse the scope and nature of the impact of security challenges in this region upon strategic communications, mainly for NATO and its member states. This study is based on the analysis of global and regional open sources regarding four key issues: terrorism, migration, illicit trafficking, and great power competition. These have been identified as macro areas that affect the entire region and are deeply influenced by information. The conclusions provide succinct recommendations on how to conduct an informed and successful STRATCOM campaign in the region.