Gordon Brown said: "I and the entire government are committed to doing everything that we can for the release of Peter Moore, whom we still believe to be alive.
"Hostage-taking is never justified and has no place in Iraq's future. I condemn it unreservedly, and once again call on the hostage-takers to release Peter Moore and give us clarity on the fates of Alec MacLachlan and Alan McMenemy."
Conservative leader David Cameron added: "The taking of hostages is utterly barbaric and must in all circumstances be condemned in the strongest possible terms.
"We fully support the government in all its efforts to secure the release of Peter Moore and achieve clarity on the fates of Alan McMenemy and Alec MacLachlan. Their families deserve nothing less."
Proof of life
After the latest reports, the families of the remaining hostages broke their silence to speak to BBC News and appeal directly to the kidnappers.
Mr Moore's stepmother Pauline Sweeney said: "I plead to the hostage takers to send home the bodies of Alec and Alan so that their parents can have closure and move on, and I appeal to them to please let Peter come back alive."
The five hostages were taken in May 2007
Mr McMenemy's wife Rosalyn added: "We continue to hope and pray that these reports cannot be true, we are desperate to have Alan home to his family - please return him so that he can return to me and his children where he belongs."
And Mr Maclachlan's ex-girlfriend and their child's mother, Hailey Williams, said: "These reports are the worst possible news for us but we continue to hope they cannot be true.
"We appeal to those holding him to please send him home to us... because as a family we can't copy with this any more."
Government officials told the families of Mr McMenemy, from Glasgow, and Mr MacLachlan, from south Wales, last week that they were probably dead.
Business Secretary Lord Mandelson said British officials were doing their "absolute level best" through a variety of channels to bring the hostages to safety.
BBC security correspondent Frank Gardner
The revelation that four out of the five British hostages in Iraq are now thought to be dead will inevitably prompt questions as to how the Foreign Office has handled this.
Britain has a longstanding policy of "not making substantive concessions to kidnappers" as the government believes it only encourages more kidnapping.
But that does not rule out secret, behind-the-scenes negotiations and earlier this year there were encouraging signs of progress.
It was hoped that with the gradual normalisation of Iraq's political scene the kidnappers would be persuaded to release their captives and that the US, which is drawing down its forces in Iraq, would gradually empty detention centres and hand over prisoners to Iraq's government.
But it seems the kidnappers, while negotiating, had already murdered some of their British captives.
They are likely to demand concessions before handing over the bodies of the latest victims.
But he added: "I don't disguise the fact that we are extremely concerned for the safety of the hostages."
A statement from all the families said: "We are all deeply upset and troubled to hear the reports that Alec and Alan have died in the hands of their captors, as well as Jason Swindlehurst and Jason Creswell.
"This is a terrible ordeal for us all. We ask those holding our men for compassion when so many are working hard for reconciliation in Iraq and we continue to pray for the safe return of our men."
Mr Moore had been working for US management consultancy Bearingpoint in Iraq. The other men were security contractors employed to guard him.
The group was captured at Baghdad's Ministry of Finance in May 2007 by about 40 men disguised as Iraqi policemen.
They are understood to belong to an obscure militia known as Islamic Shia Resistance in Iraq, which has demanded the release of up to nine of their associates held in US military custody since early 2007.
Security experts understood there had been positive diplomatic moves behind the scenes, including the release of a prisoner - whose freedom was being demanded by the hostage-takers - from detention by the Americans.
The Foreign Office insists the British government has not been directly involved in negotiations and that the Iraqi authorities have been acting as lead negotiator.
Little is known about the captives because of a media blackout during a large period of their captivity.
It originally came on the instruction of the hostage-takers who said they did not want publicity.
This has been Britain's longest running hostage crisis for nearly 20 years.
This page is best viewed in an up-to-date web browser with style sheets (CSS) enabled. While you will be able to view the content of this page in your current browser, you will not be able to get the full visual experience. Please consider upgrading your browser software or enabling style sheets (CSS) if you are able to do so.