diff --git a/swh/provenance/tests/test_routing_keys.py b/swh/provenance/tests/test_routing_keys.py
new file mode 100644
--- /dev/null
+++ b/swh/provenance/tests/test_routing_keys.py
@@ -0,0 +1,78 @@
+# Copyright (C) 2021  The Software Heritage developers
+# See the AUTHORS file at the top-level directory of this distribution
+# License: GNU General Public License version 3, or any later version
+# See top-level LICENSE file for more information
+
+from typing import Optional
+
+import pytest
+
+from swh.model.hashutil import hash_to_bytes
+from swh.provenance.api.server import ProvenanceStorageRabbitMQServer
+from swh.provenance.interface import RelationType
+
+
+@pytest.mark.parametrize(
+    "item, meth_name, relation, expected",
+    (
+        (
+            hash_to_bytes("c0d8929936631ecbcf9147be6b8aa13b13b014e4"),
+            "content_add",
+            None,
+            "content_add.unknown.c",
+        ),
+        (
+            hash_to_bytes("c0d8929936631ecbcf9147be6b8aa13b13b014e4"),
+            "relation_add",
+            RelationType.CNT_EARLY_IN_REV,
+            "relation_add.content_in_revision.c",
+        ),
+        (b"/path/1", "location_add", None, "location_add.unknown.a"),
+    ),
+)
+def test_routing_keys(
+    item: bytes, meth_name: str, relation: Optional[RelationType], expected: str
+) -> None:
+    assert (
+        ProvenanceStorageRabbitMQServer.get_routing_key(item, meth_name, relation)
+        == expected
+    )
+
+
+@pytest.mark.parametrize(
+    "item, meth_name, relation, expected",
+    (
+        (
+            hash_to_bytes("c0d8929936631ecbcf9147be6b8aa13b13b014e4"),
+            "content_add",
+            RelationType.CNT_EARLY_IN_REV,
+            "'content_add' requires 'relation' to be None",
+        ),
+        (
+            hash_to_bytes("c0d8929936631ecbcf9147be6b8aa13b13b014e4"),
+            "relation_add",
+            None,
+            "'relation_add' requires 'relation' to be provided",
+        ),
+    ),
+)
+def test_routing_key_error(
+    item: bytes, meth_name: str, relation: Optional[RelationType], expected: str
+) -> None:
+    with pytest.raises(BaseException) as ex:
+        ProvenanceStorageRabbitMQServer.get_routing_key(item, meth_name, relation)
+    assert expected in str(ex.value)
+
+
+@pytest.mark.parametrize(
+    "entity",
+    ("content", "directory", "origin", "revision"),
+)
+def test_routing_keys_range(entity: str) -> None:
+    meth_name = f"{entity}_add"
+    for range in ProvenanceStorageRabbitMQServer.get_ranges(entity):
+        id = hash_to_bytes(f"{range:x}000000000000000000000000000000000000000")
+        assert (
+            ProvenanceStorageRabbitMQServer.get_routing_key(id, meth_name, None)
+            == f"{meth_name}.unknown.{range:x}"
+        )