The Stockholm Programme sets new challenges for the Area of Freedom Security and Justice (AFSJ). The development of external relationships with European Neighbourhood Policy and the Euro-Mediterranean Economic Area countries will prove problematic. The treaty boundary lines between the Common Foreign and Security Policy and the AFSJ will need to be negotiated. In addition, the full range of EU provisions with regard to policing, investigation and prosecution, and fundamental and due process rights, all required to obtain safe convictions, which will need to be part of the EU external relations legal framework for the AFSJ. EU legal agreements for the AFSJ could be either directly with a particular third country, or via Europol. Europol counterparts could be the South-East European Law Enforcement Centre (SELEC) or the Central Asian Regional Information and Coordination Centre (CARICC). This paper will critically analyse the problems likely from an EU legal framework and policy perspective.