There are two main approaches in the global war on terrorism (GWOT). On the one hand, the hard approach entails physical engagements which cripple destructive plans by terrorists, such as bombings. Through the legislative, judiciary and executive arms of the state, the modern state uses methods such as arrest, surveillance, intelligence and detention to cripple damaging initiatives by terrorists. The soft approach, on the other hand, attempts to debase terrorist ideology through a counter-ideology discourse against radical ideologies which encourage political violence. Through the soft approach, Muslim organizations and leaders debunk terrorist's ideology of hate and violence. This article attempts to elucidate efforts made by governments, and of particular interest are contributions made by Muslim leaders in maritime Southeast Asia to counter the ideology and activities of terrorism.