diff --git a/swh/journal/serializers.py b/swh/journal/serializers.py
--- a/swh/journal/serializers.py
+++ b/swh/journal/serializers.py
@@ -160,12 +160,13 @@
 def kafka_to_value(kafka_value: bytes) -> Any:
     """Deserialize some data stored in kafka"""
     value = msgpack_loads(kafka_value)
-    if isinstance(value, list):
-        return tuple(value)
-    if isinstance(value, dict):
-        return ensure_tuples(value)
-    return value
+    return ensure_tuples(value)
 
 
-def ensure_tuples(value: Dict) -> Dict:
-    return {k: tuple(v) if isinstance(v, list) else v for k, v in value.items()}
+def ensure_tuples(value: Any) -> Any:
+    if isinstance(value, (tuple, list)):
+        return tuple(map(ensure_tuples, value))
+    elif isinstance(value, dict):
+        return dict(ensure_tuples(list(value.items())))
+    else:
+        return value
diff --git a/swh/journal/tests/journal_data.py b/swh/journal/tests/journal_data.py
--- a/swh/journal/tests/journal_data.py
+++ b/swh/journal/tests/journal_data.py
@@ -130,6 +130,7 @@
         synthetic=False,
         metadata=None,
         parents=(),
+        extra_headers=((b"foo", b"bar"),),
     ),
 ]