Although the threat of terrorism in North Africa is not a new challenge to safety and security in the region, its focus constantly changes. Recently this manifested in the name change of the Salafist Group for Preaching and Combat, commonly known as the GSPC to al-Qa’eda in the Land of the Islamic Maghreb (AQLIM). Notwithstanding the fact that this new direction was influenced by an attempt to remain relevant – therefore influenced by weakness not strength – it signalled to the international community that al-Qa’eda not openly confirmed its presence in the region, but with it came an increase in threat perception to Western interests and nationals. The following brief paper hope to place the threat to Europe and Western interest in context: Firstly in particularly Algeria, but secondly the threat presented by individuals originally from North Africa directly to European countries. The paper conclude with a call to European countries to carefully assess the medium- to long-term impact counter-measures have in the broader fight against radicalization, extremism and terrorism.