The Southeast Asian region was riddled with the threat of terrorism long before the 11 September 2001 attacks on the United States. Due to various historical developments, nature of geography, ethnic-religious make-up and the nature of regimes in the region, terrorism of different kinds, particularly associated with religious extremism, has been in vogue in Indonesia, Thailand, Myanmar and the Philippines for more than four decades. What defined the terrorist challenge was that it was national in character, attempting either to secede from the Central Government to form a new state or to force the Central Government to adopt policies that would support the raison d'etre of these extremist groups, basically that called for the establishment of a political system that was more Islamic in character, either nationally or within a specified territory within a national state. However, what has made the challenge of 'new terrorism' distinct, especially with regard to Jemaah Islamiyah (JI), is that while it aims to establish an Islamic state, its goals and organisational structures are far more wide-ranging. Unlike the terrorism and challenges of past religious extremist groups in the region, JI is a regional terrorist organisation. It wants to establish a regional Islamic state (Daulah Islamiyah) covering most of southern Southeast Asia, forming a new Islamic epicentre in the Asia-Pacific region. Additionally, JI has been able to synergise with various existing extremist groups in the region and beyond, succeeding in the process in posing the most serious security threat to the region since the end of the Cold War. What JI is, the challenge it poses, the measures that have been adopted to manage it and the long-term consequences of the JI phenomenon are analysed in this study.