US Secretary of State Colin Powell said the taped statement, which called on Muslims to defend Iraq, is proof of a link between the al-Qaeda network and the Iraqi Government.
"
America is working on dragging the world towards a great catastrophe by insisting on launching an unjust aggression on Iraq
"
Taha Yassin Ramadan
Iraqi Vice-President
But the German Government said it could not conclude from the evidence that Bin Laden is backed by Baghdad.
Analysts have meanwhile pointed out that the message calls for support for Iraq - but not the regime of Saddam Hussein, whose members are described as "infidel socialists".
Iraq itself has denied any link with al-Qaeda and a senior official accused the US of using the statement to add to its "unjust aggression" against Iraq.
Mr Powell said the tape - which US experts believe does contain Bin Laden's voice - showed that the "nexus between terrorists and states that are developing weapons of mass destruction can no longer be looked away from and ignored".
His spokesman Richard Boucher said the recording showed that Iraq and al-Qaeda were "bound by a common hatred" of America.
The al-Qaeda leader, he said, threatens everyone in the Arab world except Iraqi President Saddam Hussein.
Divided reaction
But many remain unconvinced about the veracity of the tape, and have raised doubts that it connects Bin Laden to Saddam.
"
We stress the importance of martyrdom attacks against the enemy; these attacks inflicted on America and Israel a disaster they have never experienced before
"
Voice identified as Osama Bin Laden
A German Government spokesman said: "From what is known so far, we don't think we can conclude that there is evidence of an axis or close link between the regime in Baghdad and al-Qaeda."
Iraqi Vice-President Taha Yassin Ramadan, quoted by the official Iraqi News Agency, said: "America is working on dragging the world towards a great catastrophe by insisting on launching an unjust aggression on Iraq."
BBC correspondents in the Middle East report a divided reaction.
They say the message "can only resonate" with an Arab public angry at indignities suffered by Palestinians and Iraqis.
Reuters news agency reported that almost everyone it interviewed in Mena on the penultimate day of the Hajj pilgrimage supported Bin Laden.
'Troubling message'
The broadcast will make life more difficult for governments, our correspondents say, as they walk a fine line between the anti-war feelings of their people and strong US pressure.
The BBC's Caroline Hawley in Amman says the statement was a "troubling message" for Jordan which was listed with other nations as potential "apostates" should they aid the US.
The speech, which tells Muslims to stand with the Iraqi people against the United States, was broadcast by the Arab-language television station al-Jazeera on Tuesday.
It was contained in a poor-quality audio recording in which a man's voice, alleged to be that of Bin Laden, calls for suicide attacks against Americans and resistance to any attack on Iraq.
Quoting often from the Koran, the speaker portrays US soldiers as cowards.
He claims al-Qaeda and Taleban forces held out in the Tora Bora mountain cave complex against US and Afghan forces for weeks.
The US did target Tora Bora in late 2001 as it tried to capture or kill Bin Laden, whose group is blamed for the 11 September attacks on the US and other atrocities.
'Specific threats'
The broadcast came as the UK deployed soldiers to guard London's Heathrow airport.
A senior member of the government, John Reid, said there was a threat "of the nature" of the 11 September attacks on the World Trade Center in New York.
The head of the CIA also warned of an increased risk of al-Qaeda attacks in the US and on the Arabian peninsula using a "dirty bomb" or poisons.
George Tenet said that US intelligence pointed to possible attacks in a matter of days - perhaps involving chemical or radioactive weapons.
The warning triggered panic-buying in the US, as Americans followed advice to prepare disaster kits and stock up on bottled water.