Communications firms are being asked to record all internet contacts between people as part of a modernisation in UK police surveillance tactics.
The home secretary scrapped plans for a database but wants details to be held and organised for security services.
The new system would track all e-mails, phone calls and internet use, including visits to social network sites.
The Tories said the Home Office had "buckled under Conservative pressure" in deciding against a giant database.
Announcing a consultation on a new strategy for communications data and its use in law enforcement, Jacqui Smith said there would be no single government-run database.
But she also said that "doing nothing" in the face of a communications revolution was not an option.
The Home Office will instead ask communications companies - from internet service providers to mobile phone networks - to extend the range of information they currently hold on their subscribers and organise it so that it can be better used by the police, MI5 and other public bodies investigating crime and terrorism.
Ministers say they estimate the project will cost £2bn to set up, which includes some compensation to the communications industry for the work it may be asked to do.
"Communications data is an essential tool for law enforcement agencies to track murderers, paedophiles, save lives and tackle crime," Ms Smith said.
"Advances in communications mean that there are ever more sophisticated ways to communicate and we need to ensure that we keep up with the technology being used by those who seek to do us harm.
"It is essential that the police and other crime fighting agencies have the tools they need to do their job, However to be clear, there are absolutely no plans for a single central store."
