"Thousand" of celebrities and politicians were allegedly targeted
The police are to examine claims that a huge mobile phone hacking operation was launched by the News of the World, targeting thousands of people.
The Guardian says the Sunday paper's reporters paid private investigators to hack into phones, many of them owned by politicians and celebrities.
It is alleged details were suppressed by the police and the High Court.
Prime Minister Gordon Brown said: "This raises questions that are serious and will obviously have to be answered."
Metropolitan Police Commissioner Sir Paul Stephenson has ordered a senior officer to "establish the facts".
Sir Paul said Met Assistant Commissioner John Yates would "look into that detail and I would anticipate making a statement later today perhaps".
Alleged victims of the phone-hacking operation - including former deputy prime minister John Prescott and broadcaster Andrew Neil - have complained that because they were kept in the dark about the allegations they have not been able to seek redress from the News of the World.
Lawyers said if the allegations against the News of the World were proved, the paper could face damages claims running into "many hundreds of thousands of pounds".
Home Office Minister David Hanson told MPs "serious allegations" had been made that "deserve an examination".
MPs on the House of Commons culture and media committee have also pledged to reopen their investigation into phone hacking.
John Whittingdale: "We are re-visiting the inquiry"
Committee chairman John Whittingdale said former News of the World editor Andy Coulson, who now works as director of communications for the Conservative party, was likely to be summoned to give evidence.
Mr Coulson has previously said he was unaware of any widespread hacking operation when he was editor of the paper.
The Guardian alleged Mr Prescott, London Mayor Boris Johnson, former Culture Secretary Tessa Jowell, actress Gwyneth Paltrow, model Elle Macpherson and publicist Max Clifford were among "two or three thousand" public figures targeted by the hacking operation.
But the paper says details about how widespread the operation was were suppressed by the police and the High Court.
Nick Robinson BBC political editor
David Cameron is standing by his man.
The line coming from his close allies is that he is not even contemplating asking Andy Coulson, his communications director, to resign.
One source insisted that no significant new facts had emerged since Mr Coulson had been appointed by the Tories, and said: "The past is the past. Mistakes were made but he paid a high price for them. There is a world of difference between what he did as a tabloid editor and what he does for us."
The source went on to say that if Mr Coulson was called to give evidence before the Commons media select committee "that wouldn't change our view of him at all".
The details obtained by the Guardian allegedly emerged during a court case involving Professional Footballers' Association chief executive Gordon Taylor and the News of the World.
Mr Taylor sued News Group, which owns the News of the World, on the basis that its senior executives must have known about an alleged hacking operation on his mobile phone - claims of which had emerged in a court case involving the paper's royal editor.
He received £700,000 in damages and court costs last year, but on condition that details of the case were not made public.
Mr Coulson said: "This story relates to an alleged payment made after I left the News of the World two-and-a-half-years ago. I have no knowledge whatsoever of any settlement with Gordon Taylor."
Some of the targets of the alleged phone-hacking operation vented their anger at the police and legal authorities.
Mr Neil said: "Those who have been on the receiving end of this criminal activity so far have not had recourse to justice."
Mr Prescott said "many many" questions needed to be answered.
He said: "First of all, those of us that had our phones tapped and the police were aware of it - why were we not told? Why were they [the News of the World] not prosecuted?
"Why was a separate deal done in the court and then put away, and not made available to us? To the legal authorities [I would ask] why did you do this?"
He said News Group newspaper executives had previously convinced MPs that News of the World royal editor Clive Goodman, who was jailed for hacking into mobile phones, was a "one-off" example of a "rogue" reporter.
"That was clearly untrue if these allegations are to be believed," Mr Prescott said.
Liberal Democrat home affairs spokesman Chris Huhne called for an independent inquiry.
The Information Commissioner's office said it had passed on evidence in 2008 to Mr Taylor's lawyers that 31 journalists working for the News of the World and the Sun had acquired people's personal information by underhand means or "blagging".
News International, the parent company of News Group, said it would be "inappropriate" to comment on the Guardian's allegations.
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.