Civil liberty groups and ISPs have voiced concerns over the newly-published draft communications bill.
The controversial bill extends the type of data that internet service providers must keep.
The government said that updated legislation to take account of new technology was vital in the fight against criminals and terrorists.
But activists have dubbed it a snooper's charter.
"This is all about giving the police unsupervised access to data. It is shocking for a government that opposed Labour's plans on this to propose virtually the same thing," said Jim Killock, director of the Open Rights Group.
"It will cost billions of pounds and will end up only catching the stupid or the innocent. Terrorists will circumvent it."
Publishing the bill, Home Secretary Theresa May said: "Communications data saves lives. It is a vital tool for the police to catch criminals and to protect children.
"If we stand by as technology changes, we will leave police officers fighting crime with one hand tied behind their backs.
She was keen to point out that the proposals do not include reading the content of websites, email or social networks.
"Checking communication records, not content, is a crucial part of day-to-day policing and the fingerprinting of the modern age - we are determined to ensure its continued availability in cracking down on crime," she said.
But Mr Killock argues that knowing where a citizen has been online is equally intrusive.
Drawing a parallel he said: "If I'm having an affair then who I'm talking to is just as revealing as what I say," he said.
The bill - an update to the controversial RIPA (Regulation of Investigatory Powers Act) legislation - lays out new duties for the UK communications companies.
The new proposals would require ISPs to keep details of a much wider range of data including use of social network sites, webmail, voice calls over the internet, and gaming. Websites visited could be recorded, although pages within sites would not be.
BT said that it was considering the proposals and would report back to the parliamentary committee in due course.
The Internet Service Providers' Association said that it would be lobbying MPs in the coming months.
"Ispa has concerns about the new powers to require network operators to capture and retain third party communications data," said a spokesman.
"These concerns include the scope and proportionality, privacy and data protection implications and the technical feasibility.
"Whilst we appreciate that technological developments mean that government is looking again at its communications data capabilities, it is important that powers are clear and contain sufficient safeguards," it added.
The bill faces a tough ride through parliament with Lib Dem MPs and some Conservatives calling for it to be watered down or abandoned altogether.
Trevor Pearce, director general of the Serious Organised Crime Agency (Soca), warned that any attempts to undermine the legislation would have a direct effect on policing.
"Any significant reduction in the capability of law enforcement agencies to acquire and exploit intercept intelligence and evidential communications data would lead to more unsolved murders, more firearms on our streets, more successful robberies, more unresolved kidnaps, more harm from the use of class A drugs, more illegal immigration and more unsolved serious crime overall.
"This would mean Soca, the MPS [Metropolitan Police Service] and other agencies relying more heavily on more expensive, more risky and potentially more intrusive techniques to locate and apprehend offenders."
Soca said that it uses communications data in 95% of the serious crime investigations it conducts.
Protect the Children... you don't get porn unless you type the word porn in...
Labour tried it. Conservatives stopped it.
Conservatives are trying it. Labour will not back it and the Lib-Dems who are currently in coalition with the Conservatives will vote against it or abstain...
Currently this is only a draft bill and I am pretty confident that unless a terrorist attack occurs and the fickle electorate gets into the Governments pocket again like 9/11 and 7/7 this isn't going to pass.
We've had enough bullshit of this sort with the Olympics and the fact residents have found anti-aircraft missiles on their roofs...
...fifty thousand... as in: 50,000?
Bargain. It would cost billions for the ISP's to store all the data anyway.