This paper argues that terrorism, as a national and regional threat in the Middle East, is experiencing transformations after the Arab Spring, reflecting political developments in the region and generating new patterns of terrorism, or, in some other cases, bringing old patterns to the forefront. It is becoming more complex, in terms of the actors, the strategies adopted by terrorist organizations, and the more pressing security threats. It also argues that this transformation of terrorism coincides with a lack of consensus among Middle East countries on the pressing nature of terrorism as a threat and on the needed for strategies to counter it. Therefore, encouraging any regional mechanism for countering terrorism needs to be pursued on a limited scale encompassing only countries that share the same security perceptions. In this context, the present paper examines three main challenges that regional cooperation faced in the Middle East with regard to countering terrorism in the years following the Arab revolutions. It emphasizes the factors which render a regional level approach difficult to achieve.