The European Parliament has approved rules forcing telephone companies to retain call and internet records for use in anti-terror investigations.
Individual governments will decide exactly how long to keep data
Records will be kept for up to two years under the new measures.
Police will have access to information about calls, text messages and internet data, but not exact call content.
The UK, which pressed European member states to back the rules, said that data was the "golden thread" in terrorist investigations.
The parliament voted by 378 to 197 to approve the bill, which had already been agreed by the assembly's two largest groups, the European People's Party and the Socialists.
The measures were proposed by Britain after the bomb attacks in London in July.
They still need to be formally approved by EU member states.
UK Home Secretary Charles Clarke said the approval showed the European institutions - the Parliament, the Council, the Commission - standing firm against terrorism and serious organised crime.
"This sends a powerful message that Europe is united against terrorism and organised crime," he said.
"All three institutions have worked closely together and been willing to compromise in order to reach agreement on this important measure."
The measures will require firms to store:
- data that can trace fixed or mobile telephone calls
- time and duration of calls
- location of the mobile phone being called
- details of connections made to the Internet
- details, but not the content, of internet e-mail and internet telephony services
Details of connected calls that are unanswered, which can be used as signals to accomplices or used to detonate bombs, will also be archived where that data exists.
But the telecommunications industry has raised some concerns about the measures, which firms say could be expensive to implement.
Thierry Dieu, spokesman for European Telecommunications Networks Operators' Association, said that because the proposed measures go much further than the current practices, especially for the internet data, "it is clear that there will be a lot of investment for the industry to make".
A spokesman for the Internet Service Providers' Association (ISPA) said it remained to be seen how the measures would affect providers once incorporated into UK law.
He said there was already some voluntary co-operation with the authorities, but mandatory data retention would result in significant costs. ISPs would have to create ways of holding the data, managing it and providing access to it for the authorities, he said.
"At the end of the day ISPs are not law enforcement agencies so they should not have to pay for it all," he said.