Indonesia continues to be an influential member of the Association of Southeast Asian Nations (ASEAN), but neighboring members appear unhappy with effects from the breakdown of law and order in Indonesia, including piracy and suspected terrorism. Tensions arose with Singapore in February 2002 due to Singaporean elder statesman Lee Kuan Yew's comments that Indonesia was doing little to combat terrorism and allowing Islamic militant groups to operate freely. Indonesians countered by accusing Singapore of harboring criminals who had exploited Indonesia's economy under Suharto. Singapore and Malaysia have both criticized Indonesia for allowing terror suspects to remain free.
The United States considers Indonesia a location of Al Qaeda terrorist network cells and other Islamic extremist groups which have threatened Americans. Hosting Megawati in a high-profile visit to Washington, D.C., just a week after the 11 September attacks, the Bush administration seemed eager to portray Indonesia as a moderate Islamic nation on its side in its "war on terror." Megawati's government, however, was not supportive of the U.S. bombing war in Afghanistan, or of the Bush administration's attack on Iraq in early 2003, which was opposed by massive public protests in Indonesian cities. The Bush administration appears to favor engagement with Indonesia's military as a counter to Islamic militancy, but the U.S. Congress continues a ban on direct military assistance in place since 1999's East Timor violence. Resumption of direct military aid to Indonesia by the United States is not allowed until there is formal accountability of Indonesian military officers for war crimes committed in East Timor.
Relations with Australia have been strained over Australia's dispatch of troops to protect East Timor in 1999. A February 2002 agreement between Indonesia and Australia to cooperate in fighting terrorism seemed to be an attempt to overcome that tension, and for Australian aid to Indonesia's military to fill the gap left by the United States ban. Relations with Australia—as well as Singapore and the United States— were strained following the bombing of a nightclub on the island of Bali in October 2002, as those countries felt that Megawati's government had not done enough to fight the threat of Muslim extremist terrorism. The majority of the bombing victims had been Australian tourists. Megawati, at the urging of her husband, toured the site of the bombing, but left soon afterward for a meeting in Mexico without taking further action to prevent the likelihood of more violent acts by terrorists. Indonesia's tourist industry suffered an extreme downturn in business following the bombing in Bali.
In spring (March–April) 2002, Megawati undertook a two week trip to four Asian nations: China, India, North Korea and South Korea. The Korea segment, in which she flew directly from North Korea to South Korea, defied President Bush's "axis of evil" effort to isolate the North. Megawati used her childhood acquaintance with North Korean leader Kim Jong-Il (he had accompanied his father, Kim Il-Sung on a visit to her father) to endorse recently reopened direct dialogue between the North and South. Her trip also symbolized revived Indonesian ties with China, which had been close in her father's administration but which had deteriorated under Suharto. Her overtures to China were interpreted as a strategy aimed at balancing Indonesia's economic dependence on Japan and the United States with new access to Chinese markets for Indonesian goods.