After the entry into force of the Treaty of Lisbon in 2009, and thanks to the better definition of the actors involved in external relations it provided, the European Parliament (EP) has acquired a greater role in European Union’s (EU’s) foreign policy and increased its ability to deal with countries outside the EU using existing interparliamentary meetings. This evolution of the EP has occurred while other important and related developments were taking place: the emergence of a global terrorist threat and the so-called Arab Spring, which has spanned most Arab countries since 2011. This essay aims at understanding how the EP’s diplomacy reacted to the challenge of balancing the promotion of EU values with the need for cooperation for security and stability. It uses as a case study the EP’s relations with southern Mediterranean countries (SMCs). First, a general overview of the counterterrorist activities laid down by the EP toward SMCs is provided. Then the essay focuses on the activity of EP’s delegations with the Maghreb and the Mashreq, with reference to cooperation on counterterrorism with Algeria, Egypt, Morocco, and Tunisia. Finally, concluding remarks compare the general EU approach to counterterrorism in SMCs with that of the EP, discussing some existing criticisms and highlighting that the EP proved to be a coherent actor toward SMCs.