North Africa is experiencing the emergence of various Jihadist groups that are proving to be highly capable of and effective in capitalising regional instability and advancing their political programmes and military operations at the expense of the on-going post-Arab uprisings political transition. In this context, the case of Tunisia is one of the most interesting and useful to study, both in terms of adaptation of a transitional regime to a new counter-terrorism strategy and of the influence that the EU could exert on the development of new policies in the security sector of a third country. The paper analyses EU’s counter-terrorism strategies in order to point out how the EU and its neighbourhood have traditionally dealt with violent extremist groups. Secondly, the paper focuses on how EU countries and Tunisia are responding to the terrorist threat. Finally, in order to better address the issue, the case study of Tunisia is analysed. The paper formulates some suggestions in order to develop a broader agenda the EU and regional stakeholders can pursue together in order to overcome these violent extremism threats.