diff --git a/swh/storage/in_memory.py b/swh/storage/in_memory.py
--- a/swh/storage/in_memory.py
+++ b/swh/storage/in_memory.py
@@ -318,7 +318,18 @@
                     ret[key] = content[key]
         return ret
 
-    def directory_ls(self, directory_id):
+    def _directory_ls(self, directory_id, recursive, prefix=b''):
+        if directory_id in self._directories:
+            for entry in self._directories[directory_id]['entries']:
+                ret = self._join_dentry_to_content(entry)
+                ret['name'] = prefix + ret['name']
+                ret['dir_id'] = directory_id
+                yield ret
+                if recursive and ret['type'] == 'dir':
+                    yield from self._directory_ls(
+                        ret['target'], True, prefix + ret['name'] + b'/')
+
+    def directory_ls(self, directory_id, recursive=False):
         """Get entries for one directory.
 
         Args:
@@ -328,12 +339,10 @@
         Returns:
             List of entries for such directory.
 
+        If `recursive=True`, names in the path of a dir/file not at the
+        root are concatenated with a slash (`/`).
         """
-        if directory_id in self._directories:
-            for entry in self._directories[directory_id]['entries']:
-                ret = self._join_dentry_to_content(entry)
-                ret['dir_id'] = directory_id
-                yield ret
+        yield from self._directory_ls(directory_id, recursive)
 
     def directory_entry_get_by_path(self, directory, paths):
         """Get the directory entry (either file or dir) from directory with path.
diff --git a/swh/storage/storage.py b/swh/storage/storage.py
--- a/swh/storage/storage.py
+++ b/swh/storage/storage.py
@@ -503,6 +503,9 @@
         Returns:
             List of entries for such directory.
 
+        If `recursive=True`, names in the path of a dir/file not at the
+        root are concatenated with a slash (`/`).
+
         """
         if recursive:
             res_gen = db.directory_walk(directory, cur=cur)
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
@@ -6,6 +6,7 @@
 import copy
 import datetime
 import unittest
+import itertools
 from collections import defaultdict
 from unittest.mock import Mock, patch
 
@@ -173,9 +174,9 @@
                     'perms': from_disk.DentryPerms.content,
                 },
                 {
-                    'name': b'bar',
+                    'name': b'subdir',
                     'type': 'dir',
-                    'target': b'12345678901234560000',
+                    'target': self.dir['id'],
                     'perms': from_disk.DentryPerms.directory,
                 },
                 {
@@ -683,34 +684,58 @@
 
         self.assertEqual(list(gen), [missing_cont])
 
-    def test_directory_add(self):
-        init_missing = list(self.storage.directory_missing([self.dir['id']]))
-        self.assertEqual([self.dir['id']], init_missing)
-
-        self.storage.directory_add([self.dir])
-
-        stored_data = list(self.storage.directory_ls(self.dir['id']))
-
-        data_to_store = []
-        for ent in self.dir['entries']:
-            data_to_store.append({
-                'dir_id': self.dir['id'],
+    @staticmethod
+    def _transform_entries(dir_, *, prefix=b''):
+        for ent in dir_['entries']:
+            yield {
+                'dir_id': dir_['id'],
                 'type': ent['type'],
                 'target': ent['target'],
-                'name': ent['name'],
+                'name': prefix + ent['name'],
                 'perms': ent['perms'],
                 'status': None,
                 'sha1': None,
                 'sha1_git': None,
                 'sha256': None,
                 'length': None,
-            })
+            }
+
+    def test_directory_add(self):
+        init_missing = list(self.storage.directory_missing([self.dir['id']]))
+        self.assertEqual([self.dir['id']], init_missing)
+
+        self.storage.directory_add([self.dir])
 
-        self.assertCountEqual(data_to_store, stored_data)
+        actual_data = list(self.storage.directory_ls(self.dir['id']))
+        expected_data = list(self._transform_entries(self.dir))
+        self.assertCountEqual(expected_data, actual_data)
 
         after_missing = list(self.storage.directory_missing([self.dir['id']]))
         self.assertEqual([], after_missing)
 
+    def test_directory_get_recursive(self):
+        init_missing = list(self.storage.directory_missing([self.dir['id']]))
+        self.assertEqual([self.dir['id']], init_missing)
+
+        self.storage.directory_add([self.dir, self.dir2, self.dir3])
+
+        actual_data = list(self.storage.directory_ls(
+            self.dir['id'], recursive=True))
+        expected_data = list(self._transform_entries(self.dir))
+        self.assertCountEqual(expected_data, actual_data)
+
+        actual_data = list(self.storage.directory_ls(
+            self.dir2['id'], recursive=True))
+        expected_data = list(self._transform_entries(self.dir2))
+        self.assertCountEqual(expected_data, actual_data)
+
+        actual_data = list(self.storage.directory_ls(
+            self.dir3['id'], recursive=True))
+        expected_data = list(itertools.chain(
+            self._transform_entries(self.dir3),
+            self._transform_entries(self.dir, prefix=b'subdir/')))
+        self.assertCountEqual(expected_data, actual_data)
+
     def test_directory_entry_get_by_path(self):
         # given
         init_missing = list(self.storage.directory_missing([self.dir3['id']]))
@@ -733,9 +758,9 @@
             },
             {
                 'dir_id': self.dir3['id'],
-                'name': b'bar',
+                'name': b'subdir',
                 'type': 'dir',
-                'target': b'12345678901234560000',
+                'target': self.dir['id'],
                 'sha1': None,
                 'sha1_git': None,
                 'sha256': None,