The Data Retention Directive, which was passed in 2006, ordered countries to pass laws which required telecoms providers to keep logs of user activity in a bid to help fight terrorism. Countries could choose any required retention period between six months and two years.
The German Federal Constitution Court has ruled, though, that the law passed violates the rights to privacy that citizens are guaranteed under the German constitution.
The German law implementing the Directive was passed in 2008 and has been ruled unconstitutional by the Court. Changes must be made to the law before it can operate again, it said.
The Court said that the law went further than the Directive did in ordering telecoms companies to store data. It did not say that the Directive was incapable of being implemented in a constitutionally compliant way.
It said that the law did not contain enough safeguards for the privacy of the people whose information was stored, and that Germany's data protection commissioner should have oversight of the use of the data, German newspaper Der Spiegel reported.
The case was a class action suit brought by 35,000 Germans. Court president Hans-Jürgen Papier said that the data's storage could "cause a diffusely threatening feeling of being under observation that can diminish an unprejudiced perception of one's basic rights in many areas," according to Der Spiegel.
The Directive orders telecoms firms to store the details of communication events, such as phone calls, but does not order the recording of their actual content.
It has faced opposition from digital rights activists such as the Open Rights Group over concerns for individuals' privacy, and also from EU nations.
Ireland and Slovakia took a case to the European Court of Justice (ECJ) arguing that the mechanism used to adopt the Directive was wrong. They said that it was adopted using a process used for economic laws and not the more stringent processes used for those relating to justice and security.
The ECJ backed the European Commission, though, saying that the Directive regulated economic activity and not policing activity.
The UK expanded its implementation of the Directive last year when it passed a law meaning that ISPs and telecoms providers would have to record details of internet-related communications when asked to by the Government. Previous rules had applied only to non-internet data.
The Government had previously considered then rejected plans to create a single, Government-run database containing details of web, email and phone use. It said that this was the "most effective" solution but ruled it out on privacy grounds. Privacy regulator the Information Commissioner's Office (ICO) had called the plan "a step too far for the British way of life".