Tony Blair has said claims of abuse by soldiers "will be investigated" after images that appeared to show UK troops beating Iraqi youths were published.
The paper said it obtained the footage from a "whistleblower"
The News of the World has published pictures from a video the newspaper says was shot in southern Iraq in 2004.
Mr Blair said the overwhelming majority of UK troops in Iraq behave properly and do a "great job for our country and for the wider world".
The Ministry of Defence has launched an investigation into the video images.
A military spokesman in Iraq condemned "all acts of abuse and brutality" by British troops, saying the allegations related to a "tiny number" of soldiers.
On the tape, described as a "secret home video", an unidentified cameraman is heard laughing and urging his colleagues on. It was apparently filmed for fun by a corporal.
The Ministry of Defence said it was aware of the allegations, which are being investigated by the Royal Military Police.
The prime minister, who is currently in South Africa where he is attending a summit on poverty and development, said the presence of troops in Iraq was "helping Iraq to become the democracy they want to be" and "of fundamental importance".
Meanwhile, speaking on the BBC's Sunday AM programme, Chancellor Gordon Brown said the "loyal, hard-working, decent troops" in Iraq would see the allegations as a "slight on their great work".
Those responsible would be brought to trial.
British military spokesman Flight Lieutenant Chris Thomas, based in Basra, said: "We hope that the good relations that the multi-national forces have worked very hard to develop won't be adversely affected by this material."
He said the newspaper's claims related "to only a tiny number of the 80,000 personnel that have served in Iraq".
The tape allegedly shows a disturbance in the street outside what the paper calls a military compound.
Soldiers are shown chasing youths involved in the disturbance, dragging four of them into the compound and beating them on various parts of the body with batons and kicking them, one in the genitals.
The recording is said to show an attack lasting a minute, with 42 blows counted.
The News of the World said a soldier could also be seen kicking a dead Iraqi in the face.
Home Office minister Andy Burnham told the BBC: "The pictures are shocking and that's why I think the MoD are right and I'm pleased that they've said they'll carry out a full in-depth and very quick investigation.
"That's what needs to be done so that...we can find out the facts and we can make sure that if there is serious wrongdoing then there's appropriate action taken."
The paper claims it has established the soldiers involved were British, but would not disclose which unit or regiment were allegedly involved.
It said it has made exhaustive checks to establish the video's authenticity after obtaining the footage from a whistleblower, who they declined to identify.
Managing editor Stuart Kuttner said: "We've made enquires of the source, of people around the source, of military experts, of the Ministry of Defence and beyond.
The Ministry of Defence said it was investigating the allegations
"Given that there was a slip-up by a newspaper some time ago, we've satisfied ourselves that this was an absolutely genuine article."
The Ministry of Defence said it took any allegations of abuse very seriously.
However, human rights group Amnesty International said an independent investigation was necessary, rather than one by the military police.
Mike Blakemore said: "This is a complex investigation, this simply isn't investigating a case of a brawl among troops who've had too much to drink. This is a complex matter that needs to be investigated by a competent organisation."
Among those to condemn the video were Muslim groups in Britain.
The secretary-general of the Muslim Council of Britain, Sir Iqbal Sacranie, said: "These pictures are quite appalling and demonstrate a deeply worrying breakdown in army discipline.
"Incidents like this cause enormous damage to our standing in the Muslim world and also place those British troops who are carrying out their duties conscientiously in greater peril."
Dr Imran Waheed, from the radical Islamic group Hizb ut-Tahrir Britain, said the "video footage only represents the tip of the iceberg of abuse of Iraqis".
The Islamic Human Rights Commission said that "incidents of such barbarity are not isolated but symptomatic of the military occupation of Iraq."
The Army's chief General Sir Mike Jackson launched an inquiry last year into the issue of whether pre-deployment training was adequate.
Abuse allegations had damaged the Army but a cover-up would be worse, he said.