Anlass, auf europäischer Ebene über die Vorratsdatenspeicherung nachzudenken, waren 2004 die Terroranschläge auf die Vorortzüge von Madrid. Deren Täter konnte man mithilfe der Handy-Daten ermitteln. Im Februar 2006 verabschiedete der EU-Ministerrat die Richtlinie über die Vorratsdatenspeicherung, nach der alle EU-Staaten die Telekommunikationsanbieter verpflichten müssen, die Verbindungsdaten für sechs Monate zu speichern. So lange sollen die Ermittler im Ernstfall darauf Zugriff haben können. Für Deutschland galt bis dahin, dass die Daten zu Abrechnungszwecken für drei Monate gespeichert wurden. Um die EU-Richtlinie umzusetzen, änderte der Bundestag im November 2007 die Telekommunikationsüberwachung (TKG). §113 des Telekommunikationsgesetzes regelt, dass Verkehrsdaten, die bei Inanspruchnahme von Telekommunikationsdiensten entstehen, von den Anbietern der Dienste für sechs Monate gespeichert werden. Dazu gehören unter anderem die anrufende und angerufene Telefonnummer sowie Dauer des Gesprächs. Ebenso werden Internetzugänge und E-Mail-Verkehr registriert.