By 2001 ASIO no longer had a local target. The Yugoslav ambassadors and staff all went home to their six respective states to await relocation. The war in Vietnam had led to American defeat and withdrawal. Communism and the Soviet bloc disintegrated. But asylum seekers arriving by boat increased to 4,000, most being Afghans. In 2001 the Norwegian container ship Tampa picked up 400 mainly Muslim refugees, was denied access to Christmas Island and boarded by armed Australian border guards. After detention and processing, the majority secured residence in Australia, but not before official efforts to send them elsewhere (Brennan 2003; Marr and Wilkinson 2003).

From 2001 security emphasis shifted towards Islamist terrorism, which was not organized in the same way as either the communists or the European nationalists. There were no undisputed national or local Muslim leaders in a potential Australian base approaching half a million (Chulov 2006). International contacts were varied and splintered, especially between Saudi, Pakistani and Yemeni Sunni and Iranian and Iraqui Shia, and their followers. Islamic affairs, whether terrorist, religious or business, were conducted in Arabic. This language is taught in few Australian institutions, but is the fourth most common Australian language after English. (Kabir 2005). The new enemy actually killed people (including themselves) and bombed civilians, which the Australian communists never did. This did not seriously apply in Australia, with less than a dozen deaths, including Muslims. It certainly applied to Australian jihadists in the Middle East. A handful of individual murders were enough to create serious concern in Australia. The greatest loss of Australian life was in Bali among holidaymakers.

The Islamist threat might have been overlooked until the 2001 World Trade disaster of 9/ 11 and Australian involvement in the war in Afghanistan. The replacement of the communist target by Islamist terrorists presented major challenges to ASIO, despite the expansion of a new legal system designed to enhance its work. Cooperation was strengthened between ASIO and the Federal Police as well as the state police. ASIO powers started to expand from the ASIO Legislative Amendment (Terrorism) Bill of 2002.

‘Operation Pendennis’ from 2005 to 2008 continued under these new laws and arrangements, focussing on local Muslims. Eventually 18 arrests were made and 15 successful convictions won for advocating and planning, but not implementing, terrorism (Chulov 2006).