diff --git a/debian/control b/debian/control
index f3721b7c..30157075 100644
--- a/debian/control
+++ b/debian/control
@@ -1,36 +1,42 @@
 Source: swh-storage
 Maintainer: Software Heritage developers <swh-devel@inria.fr>
 Section: python
 Priority: optional
 Build-Depends: debhelper (>= 9),
                dh-python,
                python3-all,
                python3-dateutil,
                python3-flask,
                python3-nose,
                python3-psycopg2,
                python3-requests,
                python3-setuptools,
                python3-swh.core (>= 0.0.23~),
                python3-swh.objstorage (>= 0.0.2~),
                python3-vcversioner,
                python3-swh.scheduler,
                python3-click
 Standards-Version: 3.9.6
 Homepage: https://forge.softwareheritage.org/diffusion/DSTO/
 
 Package: python3-swh.storage
 Architecture: all
 Depends: python3-swh.core (>= 0.0.23~), python3-swh.objstorage (>= 0.0.2~), ${misc:Depends}, ${python3:Depends}
 Description: Software Heritage storage utilities
 
 Package: python3-swh.storage.listener
 Architecture: all
 Depends: python3-swh.storage (= ${binary:Version}), ${misc:Depends}, ${python3:Depends}, python3-kafka (>= 1.3.1~)
 Description: Software Heritage storage listener
 
 Package: python3-swh.storage.archiver
 Architecture: all
 Depends: python3-swh.storage (= ${binary:Version}), python3-swh.scheduler,
          ${misc:Depends}, ${python3:Depends}
 Description: Software Heritage storage Archiver
+
+Package: python3-swh.storage.provenance
+Architecture: all
+Depends: python3-swh.storage (= ${binary:Version}), python3-swh.scheduler,
+         ${misc:Depends}, ${python3:Depends}
+Description: Software Heritage storage Provenance
diff --git a/debian/rules b/debian/rules
index 7baf3598..5dbaab1b 100755
--- a/debian/rules
+++ b/debian/rules
@@ -1,23 +1,26 @@
 #!/usr/bin/make -f
 
 export PYBUILD_NAME=swh.storage
 
 %:
 	dh $@ --with python3 --buildsystem=pybuild
 
 
 override_dh_install:
 	dh_install
 	for pyvers in $(shell py3versions -vr); do \
 		mkdir -p $(CURDIR)/debian/python3-swh.storage.listener/usr/lib/python$$pyvers/dist-packages/swh/storage/ ; \
 		mv $(CURDIR)/debian/python3-swh.storage/usr/lib/python$$pyvers/dist-packages/swh/storage/listener.py \
 		   $(CURDIR)/debian/python3-swh.storage.listener/usr/lib/python$$pyvers/dist-packages/swh/storage/ ; \
 		mkdir -p $(CURDIR)/debian/python3-swh.storage.archiver/usr/lib/python$$pyvers/dist-packages/swh/storage/archiver ; \
 		mv $(CURDIR)/debian/python3-swh.storage/usr/lib/python$$pyvers/dist-packages/swh/storage/archiver/* \
 		$(CURDIR)/debian/python3-swh.storage.archiver/usr/lib/python$$pyvers/dist-packages/swh/storage/archiver/ ; \
+		mkdir -p $(CURDIR)/debian/python3-swh.storage.provenance/usr/lib/python$$pyvers/dist-packages/swh/storage/provenance ; \
+		mv $(CURDIR)/debian/python3-swh.storage/usr/lib/python$$pyvers/dist-packages/swh/storage/provenance/* \
+		$(CURDIR)/debian/python3-swh.storage.provenance/usr/lib/python$$pyvers/dist-packages/swh/storage/provenance/ ; \
 	done
 
 override_dh_auto_test:
 	PYBUILD_SYSTEM=custom \
         PYBUILD_TEST_ARGS="cd {build_dir}; python{version} -m nose swh -sva '!db'" \
         dh_auto_test
diff --git a/setup.py b/setup.py
old mode 100644
new mode 100755
index 6d08fe5c..eee147c3
--- a/setup.py
+++ b/setup.py
@@ -1,37 +1,38 @@
 #!/usr/bin/env python3
 
 from setuptools import setup
 
 
 def parse_requirements():
     requirements = []
     with open('requirements.txt') as f:
         for line in f.readlines():
             line = line.strip()
             if not line or line.startswith('#'):
                 continue
             requirements.append(line)
 
     return requirements
 
 
 setup(
     name='swh.storage',
     description='Software Heritage storage manager',
     author='Software Heritage developers',
     author_email='swh-devel@inria.fr',
     url='https://forge.softwareheritage.org/diffusion/DSTO/',
     packages=[
         'swh.storage',
         'swh.storage.archiver',
         'swh.storage.api',
+        'swh.storage.provenance',
         'swh.storage.tests',
     ],
     scripts=[
         'bin/swh-storage-add-dir',
     ],
     install_requires=parse_requirements(),
     setup_requires=['vcversioner'],
     vcversioner={},
     include_package_data=True,
 )