The speech, the first formal call by Islamic State (IS) for a war against and in the West, was issued by the group's spokesman Abu Muhammad al-Adnani ash-Shami, days after anti-terrorism raids in Sydney and Brisbane.
Those raids sought to disrupt a plot by IS supporters to abduct and kill a random member of the public.
"If you can kill an American or European infidel – especially the spiteful and cursed French – or an Australian or a Canadian, or any other disbeliever from the infidel fighters ... then rely upon God and kill them in any way possible," al-Adnani said in the speech, which was uploaded to the web as an audio file.
"Do not consult with anyone and do not seek anyone's advice. Whether they are civilian or military, the same ruling applies," he said.
The speech has the appearance of a fatwa, or religious decree, which is a binding ruling for supporters.
The call comes amid a US push for an international coalition to confront the insurgents in Iraq and Syria.
US president Barack Obama launched air strikes in Iraq against IS in August and since then has been building support for a coalition. Australia was one of the first countries to join.
The international community was stunned in June when IS swept through regions of northern Iraq, capturing the major cities of Mosul and Tikrit and halting less than 50 kilometres from Baghdad.
The speech represents a significant shift for the militant group, which until now had only made scattered references to undertaking attacks outside Syria and Iraq. Australia features prominently in the message.
In a message directed at IS fighters, al-Adnani said: "Why is it that the world has united against you? Why have the nations of disbelief entrenched together against you? What threat do you pose to the distant place of Australia for it to send its legions towards you?"
IS threat a 'game changer'
The Federal Government said it was treating the threat as genuine.
Attorney-General George Brandis told the ABC's 7.30 program the threat underlined the need for last week's counter-terrorism raids and the decision to tighten security.
"That's why we have to take the threat of ISIL very seriously because as the Prime Minister has been saying all along, these people have set their face against the west in the most belligerent imaginable way. This is to be taken seriously," he said.
An expert from the Global Terrorism Research Centre, Professor Greg Barton, says he is concerned by how persuasive the message could be.
"It's lyrical like an old testament prophet," he said.
"I'm very, very worried about the persuasive power it will have on young people, including young Australians.
"It's quite a game changer - it means IS is now turning its energy outwards and will usurp the role of Al Qaeda, and I think we're seeing a lot of challenges coming form this."