diff --git a/swh/storage/storage.py b/swh/storage/storage.py
--- a/swh/storage/storage.py
+++ b/swh/storage/storage.py
@@ -1605,6 +1605,9 @@
         """Add an entry for origin origin_id in fetch_history. Returns the id
         of the added fetch_history entry
         """
+        if isinstance(origin_id, str):
+            origin_id = \
+                self.origin_get([{'url': origin_id}], db=db, cur=cur)[0]['id']
         fetch_history = {
             'origin': origin_id,
             'date': datetime.datetime.now(tz=datetime.timezone.utc),
diff --git a/swh/storage/tests/test_storage.py b/swh/storage/tests/test_storage.py
--- a/swh/storage/tests/test_storage.py
+++ b/swh/storage/tests/test_storage.py
@@ -3896,11 +3896,16 @@
 
     # Can only be tested with local storage as you can't mock
     # datetimes for the remote server
-    def test_fetch_history(self):
+    @given(strategies.booleans())
+    def test_fetch_history(self, use_url):
         origin = self.storage.origin_add_one(self.origin)
+        if use_url:
+            origin_id = self.origin['url']
+        else:
+            origin_id = origin
         with patch('datetime.datetime'):
             datetime.datetime.now.return_value = self.fetch_history_date
-            fetch_history_id = self.storage.fetch_history_start(origin)
+            fetch_history_id = self.storage.fetch_history_start(origin_id)
             datetime.datetime.now.assert_called_with(tz=datetime.timezone.utc)
 
         with patch('datetime.datetime'):