diff --git a/sql/upgrades/166.sql b/sql/upgrades/166.sql
new file mode 100644
--- /dev/null
+++ b/sql/upgrades/166.sql
@@ -0,0 +1,9 @@
+-- SWH DB schema upgrade
+-- from_version: 165
+-- to_version: 166
+-- description: add not_found status
+
+insert into dbversion(version, release, description)
+      values(166, now(), 'Work In Progress');
+
+alter type origin_visit_state add value 'not_found';
diff --git a/swh/storage/postgresql/db.py b/swh/storage/postgresql/db.py
--- a/swh/storage/postgresql/db.py
+++ b/swh/storage/postgresql/db.py
@@ -28,7 +28,7 @@
 
     """
 
-    current_version = 164
+    current_version = 166
 
     def mktemp_dir_entry(self, entry_type, cur=None):
         self._cursor(cur).execute(
diff --git a/swh/storage/sql/20-enums.sql b/swh/storage/sql/20-enums.sql
--- a/swh/storage/sql/20-enums.sql
+++ b/swh/storage/sql/20-enums.sql
@@ -18,6 +18,7 @@
   'created',
   'ongoing',
   'full',
-  'partial'
+  'partial',
+  'not_found'
 );
-comment on type origin_visit_state IS 'Possible origin visit values';
+comment on type origin_visit_state IS 'Possible origin visit status values';
diff --git a/swh/storage/sql/30-schema.sql b/swh/storage/sql/30-schema.sql
--- a/swh/storage/sql/30-schema.sql
+++ b/swh/storage/sql/30-schema.sql
@@ -17,7 +17,7 @@
 
 -- latest schema version
 insert into dbversion(version, release, description)
-      values(164, now(), 'Work In Progress');
+      values(166, now(), 'Work In Progress');
 
 -- a SHA1 checksum
 create domain sha1 as bytea check (length(value) = 20);