diff --git a/swh/provenance/origin.py b/swh/provenance/origin.py
--- a/swh/provenance/origin.py
+++ b/swh/provenance/origin.py
@@ -6,6 +6,7 @@
 from itertools import islice
 from typing import Generator, Iterable, Iterator, List, Optional, Tuple
 
+from swh.core.statsd import statsd
 from swh.model.model import Sha1Git
 
 from .archive import ArchiveInterface
@@ -42,6 +43,10 @@
         return (OriginEntry(url, snapshot) for url, snapshot in self.statuses)
 
 
+@statsd.timed(
+    metric="swh_provenance_origin_revision_layer_accesstime_seconds",
+    tags={"method": "main"},
+)
 def origin_add(
     provenance: ProvenanceInterface,
     archive: ArchiveInterface,
@@ -56,6 +61,10 @@
     provenance.flush()
 
 
+@statsd.timed(
+    metric="swh_provenance_origin_revision_layer_accesstime_seconds",
+    tags={"method": "process_revision"},
+)
 def origin_add_revision(
     provenance: ProvenanceInterface,
     origin: OriginEntry,
@@ -85,6 +94,10 @@
                 stack.append(parent)
 
 
+@statsd.timed(
+    metric="swh_provenance_origin_revision_layer_accesstime_seconds",
+    tags={"method": "check_preferred_origin"},
+)
 def check_preferred_origin(
     provenance: ProvenanceInterface,
     origin: OriginEntry,
diff --git a/swh/provenance/revision.py b/swh/provenance/revision.py
--- a/swh/provenance/revision.py
+++ b/swh/provenance/revision.py
@@ -7,6 +7,7 @@
 import os
 from typing import Generator, Iterable, Iterator, List, Optional, Tuple
 
+from swh.core.statsd import statsd
 from swh.model.model import Sha1Git
 
 from .archive import ArchiveInterface
@@ -48,6 +49,10 @@
             yield RevisionEntry(id, date=date, root=root)
 
 
+@statsd.timed(
+    metric="swh_provenance_revision_content_layer_accesstime_seconds",
+    tags={"method": "main"},
+)
 def revision_add(
     provenance: ProvenanceInterface,
     archive: ArchiveInterface,
@@ -83,6 +88,10 @@
         provenance.flush()
 
 
+@statsd.timed(
+    metric="swh_provenance_revision_content_layer_accesstime_seconds",
+    tags={"method": "process_content"},
+)
 def revision_process_content(
     archive: ArchiveInterface,
     provenance: ProvenanceInterface,
@@ -148,6 +157,10 @@
                     stack.append(child)
 
 
+@statsd.timed(
+    metric="swh_provenance_revision_content_layer_accesstime_seconds",
+    tags={"method": "flatten_directory"},
+)
 def flatten_directory(
     archive: ArchiveInterface,
     provenance: ProvenanceInterface,