Mit der Dokumentation von Verarbeitungstätigkeiten ist gemeint, dass das Unternehmen festhält, welche personenbezogenen Daten es zu welchem Zweck verarbeitet. Auch müssen bestimmte gesetzlich definierte Umstände der Verarbeitung dokumentiert werden, etwa die Speicherdauer der Daten und die für die Verarbeitung ergriffenen Schutzmaßnahmen.

Eine Kernfrage der Dokumentationspflicht ist, wann eine Datenverarbeitung im rechtlichen Sinne vorliegt. Dies ist stets dann der Fall, wenn sogenannte personenbezogene Daten verarbeitet werden – also Daten, mit denen eine Person identifiziert oder zumindest individualisiert werden kann. So handelt es sich z.B. auch beim Tracken von Websitebesuchern um eine oder mehrere Datenverarbeitungen, die zu dokumentieren sind.

Darüber hinaus stellt sich die Frage, wie genau eine Verarbeitung zu dokumentieren ist. Das verantwortliche Unternehmen sollte sich bei der Definition nicht von den Umständen bzw. Prozessschritten der Verarbeitung, sondern von deren übergeordnetem Zweck leiten lassen. Immer dort, wo ein Prozess mit eigenem Ziel vorliegt, besteht eine Datenverarbeitung. Der Zweck muss dabei hinreichend konkret formuliert sein. Auch ist ein Zweck nicht mit einer prozessualen Kategorie gleichzusetzen (etwa "Erstellen von..." oder "Einsatz von...").

Die maßgebliche Vorschrift für die Dokumentation von Verarbeitungstätigkeiten ist Art. 30 DSGVO.
Im ersten Absatz werden die Datenkategorien genannt, die der Verantwortliche zu dokumentieren hat. Ist an der Dokumentation ein sogenannter Auftragsverarbeiter beteiligt, muss dieser die in Absatz 2 benannten Datenkategorien dokumentieren. Ein Unternehmen, das nicht nur als Verantwortlicher, sondern auch als Auftragsverarbeiter Daten verarbeitet, muss entsprechend zwei Arten von Dokumentationen führen.

Resultat der Dokumentation von Verarbeitungstätigkeiten soll laut Gesetz ein "Verzeichnis" sein, in dem alle Verarbeitungen eines Unternehmens beschrieben sind. Dieses Verzeichnis kann sowohl in physischer als auch in digitaler Form (auch in Form einer Software-Lösung) geführt werden.