diff --git a/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java b/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java
--- a/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java
+++ b/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java
@@ -292,13 +292,13 @@
             if (nodeMatchesConstraints) {
                 if (nodeBuilder != null) {
                     nodeObserver.onNext(nodeBuilder.build());
-                }
 
-                if (remainingMatches >= 0) {
-                    remainingMatches--;
-                    if (remainingMatches == 0) {
-                        // We matched as many nodes as allowed
-                        throw new StopTraversalException();
+                    if (remainingMatches >= 0) {
+                        remainingMatches--;
+                        if (remainingMatches == 0) {
+                            // We matched as many nodes as allowed
+                            throw new StopTraversalException();
+                        }
                     }
                 }
             }
diff --git a/swh/graph/tests/test_http_client.py b/swh/graph/tests/test_http_client.py
--- a/swh/graph/tests/test_http_client.py
+++ b/swh/graph/tests/test_http_client.py
@@ -127,6 +127,27 @@
     assert set(actual) == set(expected)
 
 
+@pytest.mark.parametrize("max_matching_nodes", [0, 1, 2, 3, 4, 5, 10, 1 << 31])
+def test_visit_nodes_filtered_limit(graph_client, max_matching_nodes):
+    actual = list(
+        graph_client.visit_nodes(
+            "swh:1:rel:0000000000000000000000000000000000000010",
+            return_types="dir",
+            max_matching_nodes=max_matching_nodes,
+        )
+    )
+    expected = [
+        "swh:1:dir:0000000000000000000000000000000000000002",
+        "swh:1:dir:0000000000000000000000000000000000000008",
+        "swh:1:dir:0000000000000000000000000000000000000006",
+    ]
+    if max_matching_nodes == 0:
+        assert set(actual) == set(expected)
+    else:
+        assert set(actual) <= set(expected)
+        assert len(actual) == min(3, max_matching_nodes)
+
+
 def test_visit_nodes_filtered_star(graph_client):
     actual = list(
         graph_client.visit_nodes(