David Cameron faced calls last night to sack one of his most trusted advisers over allegations of illegal phone hacking. The alleged offences were carried out while Andy Coulson was Editor of the News of the World.

Mobile phones belonging to Cabinet ministers, actors, models and sports stars are claimed to have been among the targets of private investigators working for the newspaper while Mr Coulson — the Conservative Party’s director of communications — was in charge.

The News of the World was also alleged to have paid an out-of-court settlement after a legal case allegedly threatened to make public evidence of hacking. The News of the World is part of News International, which also publishes The Times.

The issue first came to court in January 2007 when Clive Goodman, a News of the World reporter, was jailed for hacking into the phones of three royal staff. Glenn Mulcaire, a private investigator, was also jailed for tapping further phones, including those of Max Clifford, the celebrity PR consultant, and Gordon Taylor, chief executive of the Professional Footballers’ Association.

According to senior sources in the Metropolitan Police quoted in The Guardian newspaper, which made the allegations, officers found evidence of News of the World staff using private investigators to obtain information from mobile phones. Police sources claimed last night that their investigation had uncovered evidence that many hundreds of mobile phone voicemail inboxes had been tapped into.

Mr Coulson said: “This story relates to an alleged payment made after I left the News of the World 2½ years ago. I have no knowledge whatsoever of any settlement with Gordon Taylor. The Mulcaire case was investigated thoroughly by the police and the Press Complaints Commission. I took full responsibility for what happened on my watch, but without my knowledge, and I resigned.” Mr Taylor did not return calls seeking a comment last night.

The Assistant Information Commissioner told The Times last night that 31 journalists had allegedly been involved in “the buying and selling of personal information”. Mick Gorrill said that his department had compiled a dossier within the past two years as part of a wider investigation into “the buying and selling of personal information”, which showed that journalists “had acquired people’s personal information through blagging”.

Obtaining phone, bank or health records and similar data is an offence under the Data Protection Act, although there is a public interest defence.

Mr Coulson became deputy editor of the News of the World in 2003 and was promoted to Editor the same year. He resigned in January 2007 after Mr Goodman’s sentence, but always maintained that he was unaware of the actions of his reporter.

Yesterday he faced fresh questions about his involvement in the affair. John Prescott, the former Deputy Prime Minister, who along with Tessa Jowell, now Cabinet Office Minister, was named as a target of the hacking, said it was absolutely staggering that Mr Coulson should have gone to work for the Tory party in the first place. “I hope Mr Cameron will clear him out,” he said.

Alastair Campbell, the former Director of Communications for Tony Blair, said Mr Cameron should find out quickly whether Mr Coulson acted improperly and “act accordingly”.

A spokeswoman for Mr Cameron said that the Tory leader was “relaxed” about the allegations.

John Whittingdale, Conservative chairman of the Commons Culture Select Committee, said it would consider the alleged revelations today. He told Channel 4 News: “I am concerned.” Geoff Hoon, a former Cabinet minister, said: “It is hard to see how in these circumstances Andy Coulson can continue as David Cameron’s communications chief.”

The claims will also put pressure on the Metropolitan Police, over whether they alerted all those whose phones they found had been targeted. Mr Prescott said it was “staggering” he was not alerted, adding it would “reflect very badly on the police”.

Police sources said that detectives contacted everyone they could trace over the possible tampering with their phones. Another obstacle to further prosecutions was that many of the public figures did not want to pursue the issues through the courts.

A source said: “People were pleased we had found out what had happened but they didn’t want to take it any further — the reaction of many was ‘thank you, but get rid of it’.”

A Scotland Yard spokesman said: “The Metropolitan Police Service carried out an investigation into the alleged unlawful interception of telephone calls. Officers liaised closely with the Crown Prosecution Service. Two people were charged and subsequently convicted and jailed. We are not prepared to comment further.”

Times Recommends

• Queen uses Christmas speech to praise Forces
• Helmand Christmas — the briefest of respites
• Hard work — but the finest bacon