This brief paper considers the political and social implications of the manner in which Australia has prosecuted the so-called ‘war on terror’. It does this by investigating relevant aspects of Australia’s anti-terrorism legislation and the performance of Australian security and law enforcement agencies, namely, the Australian Security and Intelligence Organisation (ASIO) and the Australian Federal Police (AFP). Focusing on the Haneef and Ul-Haque cases, the paper will consider how the political climate created by the former Federal Government’s legislative approach to the war on terror has influenced the performance of these organisations. By focusing on these two cases, the paper will demonstrate how racial, ethnic and religious stereotyping have informed and shaped Australia’s conduct of the war on terror. It will investigate the real potential for social division, and heightened national insecurity, that flows from the use and propagation of these stereotypes. The paper will also highlight the unfairness and prejudice that are inherent to racial and religious stereotyping. Finally, the paper will consider whether the Rudd Labor Government’s approach thus far to the war on terror differs in any significant measure from that of its predecessor and evaluate the prospects for real, progressive change.