The judgment was made in a case in which two British MPs had initially challenged the UK's Data Retention and Investigatory Powers Act that forced telcos to store customers' communication records for 12 months, The Guardian reported.
That law was recently replaced by the Investigatory Powers Act, otherwise known as the snooper's charter, and is expected to come into force soon.
The European Court of Justice ruled that only targeted interception of traffic and location data for the purpose of fighting serious crime, including terrorism, was justified.
The case will now come back to the UK court of appeal which will interpret the judgment in terms of British domestic law and what it will mean for the Snooper's Charter.
The ECJ said in its judgment: "Given the seriousness of the interference in the fundamental rights concerned represented by national legislation which, for the purpose of fighting crime, provides for the retention of traffic and location data, only the objective of fighting serious crime is capable of justifying such a measure."
It added: "Further, while the effectiveness of the fight against serious crime, in particular organised crime and terrorism, may depend to a great extent on the use of modern investigation techniques, such an objective of general interest, however fundamental it may be, cannot in itself justify that national legislation providing for the general and indiscriminate retention of all traffic and location data should be considered to be necessary for the purposes of that fight."
A British Home Office spokesman said the government was disappointed by the ECJ ruling.
"We are disappointed with the judgment from the European court of justice and will be considering its potential implications," a spokesperson said.
"The government will be putting forward robust arguments to the court of appeal about the strength of our existing regime for communications data retention and access."