Die Einhaltung des Bundesdatenschutzgesetzes durch nicht-öffentliche Stellen wird von den zuständigen Aufsichtsbehörden der Bundesländer kontrolliert. In der Regel sind dies die Landesdatenschutzbeauftragten. Die örtliche Zuständigkeit richtet sich grundsätzlich danach, in welchem Bundesland die datenverarbeitende Stelle ihren Sitz hat.
Die Befugnisse und Aufgaben der Aufsichtsbehörden regelt § 38 BDSG. Danach sind die Aufsichtsbehörden neben ihrer Kontrollfunktion auch beratend für die datenverarbeitenden Stellen und deren (betriebliche) Datenschutzbeauftragte tätig. In diesem Rahmen veröffentlichen sie auch zahlreiche Handreichungen zu datenschutzrechtlichen Themen.
Die Aufsichtsbehörden haben zur Ausübung der Kontrolle weitreichende Auskunfts-, Zutritts- und Prüfungsrechte. Im Fall von Verstößen gegen das Datenschutzrecht können Sie die deren Behebung anordnen und ggf. Datenverarbeitungsverfahren ganz untersagen. Auch die Verhängung von Bußgeldern nach § 43 BDSG ist möglich, der Bußgeldrahmen beträgt dabei in den meisten Fällen bis zu dreihunderttausend Euro.