diff --git a/java/server/pom.xml b/java/server/pom.xml
--- a/java/server/pom.xml
+++ b/java/server/pom.xml
@@ -18,6 +18,11 @@
 
     <dependencies>
         <dependency>
+            <groupId>ch.qos.logback</groupId>
+            <artifactId>logback-classic</artifactId>
+            <version>1.2.3</version>
+        </dependency>
+        <dependency>
             <groupId>junit</groupId>
             <artifactId>junit</artifactId>
             <version>4.11</version>
diff --git a/java/server/src/main/java/org/softwareheritage/graph/Endpoint.java b/java/server/src/main/java/org/softwareheritage/graph/Endpoint.java
--- a/java/server/src/main/java/org/softwareheritage/graph/Endpoint.java
+++ b/java/server/src/main/java/org/softwareheritage/graph/Endpoint.java
@@ -2,6 +2,9 @@
 
 import java.util.ArrayList;
 
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
 import org.softwareheritage.graph.Graph;
 import org.softwareheritage.graph.SwhId;
 import org.softwareheritage.graph.SwhPath;
@@ -20,6 +23,8 @@
   Graph graph;
   /** Internal traversal API */
   Traversal traversal;
+  /** Timings logger */
+  private static final Logger logger = LoggerFactory.getLogger(Graph.class);
 
   /**
    * Constructor.
@@ -40,10 +45,13 @@
    * @return a list of corresponding SWH PIDs
    */
   private ArrayList<SwhId> convertNodesToSwhIds(ArrayList<Long> nodeIds) {
+    long startTime = System.nanoTime();
     ArrayList<SwhId> swhIds = new ArrayList<>();
     for (long nodeId : nodeIds) {
       swhIds.add(graph.getSwhId(nodeId));
     }
+    long duration = System.nanoTime() - startTime;
+    logger.debug("convertNodesToSwhIds() took {} ns.", duration);
     return swhIds;
   }
 
@@ -55,10 +63,13 @@
    * @see org.softwareheritage.graph.SwhPath
    */
   private SwhPath convertNodesToSwhPath(ArrayList<Long> nodeIds) {
+    long startTime = System.nanoTime();
     SwhPath path = new SwhPath();
     for (long nodeId : nodeIds) {
       path.add(graph.getSwhId(nodeId));
     }
+    long duration = System.nanoTime() - startTime;
+    logger.debug("convertNodesToSwhPath() took {} ns.", duration);
     return path;
   }
 
@@ -70,10 +81,13 @@
    * @see org.softwareheritage.graph.SwhPath
    */
   private ArrayList<SwhPath> convertPathsToSwhIds(ArrayList<ArrayList<Long>> pathsNodeId) {
+    long startTime = System.nanoTime();
     ArrayList<SwhPath> paths = new ArrayList<>();
     for (ArrayList<Long> path : pathsNodeId) {
       paths.add(convertNodesToSwhPath(path));
     }
+    long duration = System.nanoTime() - startTime;
+    logger.debug("convertPathsToSwhIds() took {} ns.", duration);
     return paths;
   }
 
@@ -87,7 +101,12 @@
    */
   public ArrayList<SwhId> leaves(SwhId src) {
     long srcNodeId = graph.getNodeId(src);
+
+    long startTime = System.nanoTime();
     ArrayList<Long> nodeIds = traversal.leaves(srcNodeId);
+    long duration = System.nanoTime() - startTime;
+    logger.debug("leaves({}) took {} ns.", src, duration);
+
     return convertNodesToSwhIds(nodeIds);
   }
 
@@ -101,7 +120,12 @@
    */
   public ArrayList<SwhId> neighbors(SwhId src) {
     long srcNodeId = graph.getNodeId(src);
+
+    long startTime = System.nanoTime();
     ArrayList<Long> nodeIds = traversal.neighbors(srcNodeId);
+    long duration = System.nanoTime() - startTime;
+    logger.debug("neighbors({}) took {} ns.", src, duration);
+
     return convertNodesToSwhIds(nodeIds);
   }
 
@@ -124,11 +148,19 @@
     try {
       SwhId dstSwhId = new SwhId(dstFmt);
       long dstNodeId = graph.getNodeId(dstSwhId);
+
+      long startTime = System.nanoTime();
       nodeIds = traversal.walk(srcNodeId, dstNodeId, algorithm);
+      long duration = System.nanoTime() - startTime;
+      logger.debug("walk({}) took {} ns.", src, duration);
     } catch (IllegalArgumentException ignored1) {
       try {
         Node.Type dstType = Node.Type.fromStr(dstFmt);
+
+        long startTime = System.nanoTime();
         nodeIds = traversal.walk(srcNodeId, dstType, algorithm);
+        long duration = System.nanoTime() - startTime;
+        logger.debug("walk({}) took {} ns.", src, duration);
       } catch (IllegalArgumentException ignored2) { }
     }
 
@@ -145,7 +177,12 @@
    */
   public ArrayList<SwhId> visitNodes(SwhId src) {
     long srcNodeId = graph.getNodeId(src);
+
+    long startTime = System.nanoTime();
     ArrayList<Long> nodeIds = traversal.visitNodes(srcNodeId);
+    long duration = System.nanoTime() - startTime;
+    logger.debug("visitNodes({}) took {} ns.", src, duration);
+
     return convertNodesToSwhIds(nodeIds);
   }
 
@@ -160,7 +197,12 @@
    */
   public ArrayList<SwhPath> visitPaths(SwhId src) {
     long srcNodeId = graph.getNodeId(src);
+
+    long startTime = System.nanoTime();
     ArrayList<ArrayList<Long>> paths = traversal.visitPaths(srcNodeId);
+    long duration = System.nanoTime() - startTime;
+    logger.debug("visitPaths({}) took {} ns.", src, duration);
+
     return convertPathsToSwhIds(paths);
   }
 }