diff --git a/swh/graph/tests/test_api_client.py b/swh/graph/tests/test_api_client.py
new file mode 100644
--- /dev/null
+++ b/swh/graph/tests/test_api_client.py
@@ -0,0 +1,136 @@
+import os
+import subprocess
+import time
+import unittest
+
+import pytest
+
+from swh.graph.client import RemoteGraphClient
+
+
+@pytest.fixture(scope='module')
+def service():
+    java_dir = os.path.join('java', 'server')
+
+    # Compile Java server using maven
+    pom_path = os.path.join(java_dir, 'pom.xml')
+    subprocess.run(
+        ['mvn', '-f', pom_path, 'compile', 'assembly:single'], check=True)
+
+    # Start Java server
+    jar_path = os.path.join(
+        java_dir, 'target', 'swh-graph-1.0-jar-with-dependencies.jar')
+    graph_path = os.path.join(
+        java_dir, 'src', 'test', 'dataset', 'output', 'example')
+    server = subprocess.Popen([
+        'java', '-cp', jar_path,
+        'org.softwareheritage.graph.App', graph_path
+    ])
+
+    # Make sure the server is entirely started before running the client
+    time.sleep(1)
+
+    # Start Python client
+    localhost = 'http://0.0.0.0:5009'
+    client = RemoteGraphClient(localhost)
+
+    yield (server, client)
+
+    print('Service teardown')
+    server.kill()
+
+
+class TestEndpoints(unittest.TestCase):
+    @pytest.fixture(autouse=True)
+    def init_service(self, service):
+        (self.server, self.client) = service
+
+    def test_leaves(self):
+        actual = self.client.leaves(
+            'swh:1:ori:0000000000000000000000000000000000000021'
+        )
+        expected = [
+            'swh:1:cnt:0000000000000000000000000000000000000001',
+            'swh:1:cnt:0000000000000000000000000000000000000004',
+            'swh:1:cnt:0000000000000000000000000000000000000005',
+            'swh:1:cnt:0000000000000000000000000000000000000007'
+        ]
+        self.assertCountEqual(expected, actual)
+
+    def test_neighbors(self):
+        actual = self.client.neighbors(
+            'swh:1:rev:0000000000000000000000000000000000000009',
+            direction='backward'
+        )
+        expected = [
+            'swh:1:snp:0000000000000000000000000000000000000020',
+            'swh:1:rel:0000000000000000000000000000000000000010',
+            'swh:1:rev:0000000000000000000000000000000000000013'
+        ]
+        self.assertCountEqual(expected, actual)
+
+    def test_stats(self):
+        stats = self.client.stats()
+
+        for outer_key in ['counts', 'ratios', 'indegree', 'outdegree']:
+            self.assertIn(outer_key, stats)
+
+        for inner_key in ['nodes', 'edges']:
+            self.assertIn(inner_key, stats['counts'])
+        for inner_key in ['compression', 'bits_per_node', 'bits_per_edge',
+                          'avg_locality']:
+            self.assertIn(inner_key, stats['ratios'])
+        for inner_key in ['min', 'max', 'avg']:
+            self.assertIn(inner_key, stats['indegree'])
+            self.assertIn(inner_key, stats['outdegree'])
+
+    def test_visit_nodes(self):
+        actual = self.client.visit_nodes(
+            'swh:1:rel:0000000000000000000000000000000000000010',
+            edges='rel:rev,rev:rev'
+        )
+        expected = [
+            'swh:1:rel:0000000000000000000000000000000000000010',
+            'swh:1:rev:0000000000000000000000000000000000000009',
+            'swh:1:rev:0000000000000000000000000000000000000003'
+        ]
+        self.assertCountEqual(expected, actual)
+
+    def test_visit_paths(self):
+        actual = self.client.visit_paths(
+            'swh:1:snp:0000000000000000000000000000000000000020',
+            edges='snp:*,rev:*'
+        )
+        expected = [
+            [
+                'swh:1:snp:0000000000000000000000000000000000000020',
+                'swh:1:rev:0000000000000000000000000000000000000009',
+                'swh:1:rev:0000000000000000000000000000000000000003',
+                'swh:1:dir:0000000000000000000000000000000000000002'
+            ],
+            [
+                'swh:1:snp:0000000000000000000000000000000000000020',
+                'swh:1:rev:0000000000000000000000000000000000000009',
+                'swh:1:dir:0000000000000000000000000000000000000008'
+            ],
+            [
+                'swh:1:snp:0000000000000000000000000000000000000020',
+                'swh:1:rel:0000000000000000000000000000000000000010'
+            ]
+        ]
+        self.assertCountEqual(expected, actual)
+
+    def test_walk(self):
+        actual = self.client.walk(
+            'swh:1:dir:0000000000000000000000000000000000000016', 'rel',
+            edges='dir:dir,dir:rev,rev:*',
+            direction='backward',
+            traversal='bfs'
+        )
+        expected = [
+            'swh:1:dir:0000000000000000000000000000000000000016',
+            'swh:1:dir:0000000000000000000000000000000000000017',
+            'swh:1:rev:0000000000000000000000000000000000000018',
+            'swh:1:rel:0000000000000000000000000000000000000019'
+        ]
+        self.assertCountEqual(expected, actual)