Tony Blair said the capture of Saddam Hussein had given the Iraqi people an opportunity to unite and move forward.
Saddam pictured after his capture by US forces
The UK prime minister said he hoped the ex-leader's capture showed the "tiny minority of Iraqis" who wanted him back in power that their cause was futile.
It would now be down to the Iraqi people to decide Saddam's fate.
Mr Blair praised the US-led intelligence and military forces for seizing Saddam, who was found on Saturday in a house near Tikrit.
"This is very good news for the people of Iraq - it removes the shadow that has been hanging over them for too long of the nightmare of a return to the Saddam regime," he said.
"This fear is now removed."
The prime minister was told of the capture of Saddam at around 0900 GMT on Sunday.
He returned to Westminster from his country retreat, Chequers, before speaking to President George W Bush.
Mr Blair then appeared at a news conference in Downing Street where he told reporters: "Saddam is gone from power. He won't be coming back, that the Iraqi people now know, and it is they who will decide his fate.
"The coalition needs an Iraq that is stable and prosperous, for the good of the region and the wider world."
BBC political correspondent James Landale said Saddam's capture would relieve some of the pressure Mr Blair had suffered over the failure to find weapons of mass destruction, the worsening security situation and lingering questions about the Hutton inquiry.
Conservative leader Michael Howard said Saddam's capture was "truly excellent news".
"We must all hope that this will bring real peace in Iraq very much closer," he said.
Liberal Democrat leader Charles Kennedy said Saddam had to answer for crimes against the Iraqi people and the international community.
But he warned: "It must be remembered in the euphoria following his capture that his loyalists remain a fanatical band who may not give up their struggle immediately despite his capture."
Mr Blair's Iraq envoy, Labour MP Ann Clwyd, said she hoped that Saddam would face justice in Iraq.
Saddam undergoing medical examination
"The fact that he has been caught alive is very important because the hope now is that he will face a tribunal," she said.
European Commissioner and former Labour leader Neil Kinnock said the arrest would mean "absolute unreserved celebration for me and for millions of others".
But MP George Galloway, kicked out of the Labour Party in October after a television interview in which he fiercely condemned military action in Iraq, was sceptical that it would change any critics' mind.
Speaking from Egypt, he told BBC News 24: "It might be seized upon by the prime minister as something to laugh about, but I very much doubt if it will be the last laugh, because the truth is the country was taken into the war on the basis of a lie."
There was jubilation amongst British forces in Iraq, with soldiers talking of the "perfect Christmas present".
RAF soldier Dave Coombs said there was "immense relief" among British personnel in the southern Iraqi city of Basra and that ordinary people shared the sentiment.
"Everyone is ecstatic. People are running around, jumping up and down and dancing. They have been stopping coaches and getting people out to dance with them.
"But now they are desperate to see justice; the biggest thing they want to see now is his trial."