This chapter discusses the years 2002 and 2003, which were the first test of credibility for the EU’s new counter-terrorism agenda. The first section summarises the formal progress on the Anti-terrorism Roadmap at the EU level and discusses its implementation record at lower national or operational levels. The second section presents new initiatives beyond the Antiterrorism Roadmap and focuses on attempts to address the deficits and crises in the EU’s external counter-terrorism effort. Each section presents the EU’s internal and external counter-terrorism policies in thematic sequence. As regards the EU’s internal counter-terrorism effort, the Spanish EU Presidency in the first half of 2002 is discussed most extensively. On the external front, most attention will be given to the Greek Presidency in the first half of 2003, which coincided with the Iraq War as well as a number of important developments with regard to the EU’s external counter-terrorism cooperation. Overall, it is argued that the EU’s new counter-terrorism agenda quickly turned out to be unrealistic and was overshadowed by new political crises. This growing stagnation was only partially offset by increasing US pressure for controversial border security policies. All these trends can be understood against the background of the dynamics that informed the EU’s response to 9/11 in 2001.