Self-regulation of the media has "failed" and politicians must act to ensure "business as usual" is not an option, Harriet Harman has said.
Labour's deputy leader told BBC One's Andrew Marr Show politicians of all parties should unite to change the law to ensure a "truly independent" body is established to look at complaints.
The Leveson Inquiry on press standards is deciding its recommendations.
Opponents of statutory regulation say it would undermine freedom of speech.
The Leveson Inquiry, led by Lord Justice Leveson, was set up after allegations of widespread wrongdoing by the press, including the hacking of missing schoolgirl Milly Dowler's mobile phone.
It heard from politicians, celebrities, media figures, police and others over an eight-month period.
The inquiry is due to publish a report by the end of 2012 in which it will make recommendations on the future regulation of the press and conduct between the press, politicians and police.
Prime Minister David Cameron has committed himself to implementing these.
But, in recent weeks, campaigners for a statutory system of regulation, including the actor Hugh Grant, have voiced concern that this might not happen.
'No prior restraint'
Speaking on BBC One's Andrew Marr Show, Ms Harman said: "I don't think self-regulation of the media should be given another chance. It's absolutely clear Leveson has given a great many revelations...
"It's clear that business as usual has nothing to obtain. The status quo has failed. There's not a proper press complaints system that ensures, where the press gets it wrong, the individual can complain and that will be looked at."
She added: "Self-regulation is business as usual. That's what has failed."
But Ms Harman insisted press freedom had to be maintained within the new framework of regulation, with censorship avoided, saying: "We ought to be clear that there can be no prior restraint."
She said: "We don't want any obstruction on press freedom... I have always argued for press freedom.
"We may need a statute to underline a truly independent press freedom."
She added: "There's every possibility of getting a cross-party agreement. This should not be a political football... We don't want politicians settle scores against the press who have been bruising them... The status quo is not acceptable."
But Communities Secretary Eric Pickles told Sky News: "I think it is really massively important to ensure we have freedom of press in this country."
He added: "I think it was Thomas Jefferson who said that for a free society to operate, then the 'river of a free press' had to 'flow without restriction'.
"I think, given that the press are looking towards finding ways, the end result of offering a good way that people who have a legitimate complaint can find recourse, then that is right.
"We should be very, very, very reluctant to take on legislation. It's a balance and my view is that we should always balance in favour of a free press."
Earlier this month Mr Cameron said he did not want "heavy-handed state intervention", adding: "We have got to have a free press."
And Conservative London Mayor Boris Johnson said the "free, dynamic, irreverent and independent media that we have" was "one of the glories of this country".
The Leveson Inquiry was set up to examine the culture, practice and ethics of the press, with the first stage examining relationships the press has with public, politicians and police.
A second part of the inquiry, looking into the extent of unlawful or improper conduct within News International and other newspaper media organisations, will not get under way until police investigations are concluded.