diff --git a/Documentation/rest-api.txt b/Documentation/rest-api.txt
index 97cca38..8f6a47b 100644
--- a/Documentation/rest-api.txt
+++ b/Documentation/rest-api.txt
@@ -210,6 +210,15 @@
   GET /changes/myProject~master~I8473b95934b5732ac55d26311a706c9c2bde9940/suggest_reviewers?trace&q=J
 ----
 
+Alternatively request tracing can also be enabled by setting the
+`X-Gerrit-Trace` header:
+
+.Example Request
+----
+  GET /changes/myProject~master~I8473b95934b5732ac55d26311a706c9c2bde9940/suggest_reviewers?q=J
+  X-Gerrit-Trace: issue/123
+----
+
 Enabling tracing results in additional logs with debug information that
 are written to the `error_log`. All logs that correspond to the traced
 request are associated with the trace ID. The trace ID is returned with
diff --git a/Documentation/user-request-tracing.txt b/Documentation/user-request-tracing.txt
index ac09d3c..8430e97 100644
--- a/Documentation/user-request-tracing.txt
+++ b/Documentation/user-request-tracing.txt
@@ -11,10 +11,10 @@
 request type:
 
 * REST API: For REST calls tracing can be enabled by setting the
-  `trace` request parameter, the trace ID is returned as
-  `X-Gerrit-Trace` header. More information about this can be found in
-  the link:rest-api.html#tracing[Request Tracing] section of the
-  link:rest-api.html[REST API documentation].
+  `trace` request parameter or the `X-Gerrit-Trace` header, the trace
+  ID is returned as `X-Gerrit-Trace` header. More information about
+  this can be found in the link:rest-api.html#tracing[Request Tracing]
+  section of the link:rest-api.html[REST API documentation].
 * SSH API: For SSH calls tracing can be enabled by setting the
   `--trace` option. More information about this can be found in
   the link:cmd-index.html#trace[Trace] section of the
diff --git a/java/com/google/gerrit/acceptance/HttpResponse.java b/java/com/google/gerrit/acceptance/HttpResponse.java
index 6c03793..3e98d71 100644
--- a/java/com/google/gerrit/acceptance/HttpResponse.java
+++ b/java/com/google/gerrit/acceptance/HttpResponse.java
@@ -14,13 +14,16 @@
 
 package com.google.gerrit.acceptance;
 
+import static com.google.common.collect.ImmutableList.toImmutableList;
 import static java.nio.charset.StandardCharsets.UTF_8;
 
 import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
 import java.io.IOException;
 import java.io.InputStreamReader;
 import java.io.Reader;
 import java.nio.ByteBuffer;
+import java.util.Arrays;
 import org.apache.http.Header;
 import org.eclipse.jgit.util.IO;
 import org.eclipse.jgit.util.RawParseUtils;
@@ -61,6 +64,13 @@
     return hdr != null ? hdr.getValue() : null;
   }
 
+  public ImmutableList<String> getHeaders(String name) {
+    return Arrays.asList(response.getHeaders(name))
+        .stream()
+        .map(Header::getValue)
+        .collect(toImmutableList());
+  }
+
   public boolean hasContent() {
     Preconditions.checkNotNull(response, "Response is not initialized.");
     return response.getEntity() != null;
diff --git a/java/com/google/gerrit/httpd/restapi/RestApiServlet.java b/java/com/google/gerrit/httpd/restapi/RestApiServlet.java
index 38fe0e2..10f2638 100644
--- a/java/com/google/gerrit/httpd/restapi/RestApiServlet.java
+++ b/java/com/google/gerrit/httpd/restapi/RestApiServlet.java
@@ -110,6 +110,7 @@
 import com.google.gerrit.server.cache.PerThreadCache;
 import com.google.gerrit.server.config.GerritServerConfig;
 import com.google.gerrit.server.git.LockFailureException;
+import com.google.gerrit.server.logging.RequestId;
 import com.google.gerrit.server.logging.TraceContext;
 import com.google.gerrit.server.permissions.GlobalPermission;
 import com.google.gerrit.server.permissions.PermissionBackend;
@@ -1322,11 +1323,42 @@
   }
 
   private TraceContext enableTracing(HttpServletRequest req, HttpServletResponse res) {
-    String traceValue = req.getParameter(ParameterParser.TRACE_PARAMETER);
-    return TraceContext.newTrace(
-        traceValue != null,
-        traceValue,
-        (tagName, traceId) -> res.setHeader(X_GERRIT_TRACE, traceId.toString()));
+    // There are 2 ways to enable tracing for REST calls:
+    // 1. by using the 'trace' or 'trace=<trace-id>' request parameter
+    // 2. by setting the 'X-Gerrit-Trace:' or 'X-Gerrit-Trace:<trace-id>' header
+    String traceValueFromHeader = req.getHeader(X_GERRIT_TRACE);
+    String traceValueFromRequestParam = req.getParameter(ParameterParser.TRACE_PARAMETER);
+    boolean doTrace = traceValueFromHeader != null || traceValueFromRequestParam != null;
+
+    // Check whether no trace ID, one trace ID or 2 different trace IDs have been specified.
+    String traceId1;
+    String traceId2;
+    if (!Strings.isNullOrEmpty(traceValueFromHeader)) {
+      traceId1 = traceValueFromHeader;
+      if (!Strings.isNullOrEmpty(traceValueFromRequestParam)
+          && !traceValueFromHeader.equals(traceValueFromRequestParam)) {
+        traceId2 = traceValueFromRequestParam;
+      } else {
+        traceId2 = null;
+      }
+    } else {
+      traceId1 = Strings.emptyToNull(traceValueFromRequestParam);
+      traceId2 = null;
+    }
+
+    // Use the first trace ID to start tracing. If this trace ID is null, a trace ID will be
+    // generated.
+    TraceContext traceContext =
+        TraceContext.newTrace(
+            doTrace,
+            traceId1,
+            (tagName, traceId) -> res.setHeader(X_GERRIT_TRACE, traceId.toString()));
+    // If a second trace ID was specified, add a tag for it as well.
+    if (traceId2 != null) {
+      traceContext.addTag(RequestId.Type.TRACE_ID, traceId2);
+      res.addHeader(X_GERRIT_TRACE, traceId2);
+    }
+    return traceContext;
   }
 
   private boolean isDelete(HttpServletRequest req) {
diff --git a/javatests/com/google/gerrit/acceptance/rest/TraceIT.java b/javatests/com/google/gerrit/acceptance/rest/TraceIT.java
index b48d47e..4de54e3 100644
--- a/javatests/com/google/gerrit/acceptance/rest/TraceIT.java
+++ b/javatests/com/google/gerrit/acceptance/rest/TraceIT.java
@@ -18,6 +18,7 @@
 import static org.apache.http.HttpStatus.SC_CREATED;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.gerrit.acceptance.AbstractDaemonTest;
 import com.google.gerrit.acceptance.PushOneCommit;
@@ -36,6 +37,7 @@
 import com.google.gerrit.server.validators.ValidationException;
 import com.google.inject.Inject;
 import java.util.List;
+import org.apache.http.message.BasicHeader;
 import org.junit.After;
 import org.junit.Before;
 import org.junit.Test;
@@ -71,29 +73,90 @@
     assertThat(response.getStatusCode()).isEqualTo(SC_CREATED);
     assertThat(response.getHeader(RestApiServlet.X_GERRIT_TRACE)).isNull();
     assertThat(projectCreationListener.traceId).isNull();
-    assertThat(projectCreationListener.foundTraceId).isFalse();
     assertThat(projectCreationListener.isLoggingForced).isFalse();
   }
 
   @Test
-  public void restCallWithTrace() throws Exception {
+  public void restCallWithTraceRequestParam() throws Exception {
     RestResponse response =
         adminRestSession.put("/projects/new2?" + ParameterParser.TRACE_PARAMETER);
     assertThat(response.getStatusCode()).isEqualTo(SC_CREATED);
     assertThat(response.getHeader(RestApiServlet.X_GERRIT_TRACE)).isNotNull();
     assertThat(projectCreationListener.traceId).isNotNull();
-    assertThat(projectCreationListener.foundTraceId).isTrue();
     assertThat(projectCreationListener.isLoggingForced).isTrue();
   }
 
   @Test
-  public void restCallWithTraceAndProvidedTraceId() throws Exception {
+  public void restCallWithTraceRequestParamAndProvidedTraceId() throws Exception {
     RestResponse response =
         adminRestSession.put("/projects/new3?" + ParameterParser.TRACE_PARAMETER + "=issue/123");
     assertThat(response.getStatusCode()).isEqualTo(SC_CREATED);
-    assertThat(response.getHeader(RestApiServlet.X_GERRIT_TRACE)).isNotNull();
+    assertThat(response.getHeader(RestApiServlet.X_GERRIT_TRACE)).isEqualTo("issue/123");
     assertThat(projectCreationListener.traceId).isEqualTo("issue/123");
-    assertThat(projectCreationListener.foundTraceId).isTrue();
+    assertThat(projectCreationListener.isLoggingForced).isTrue();
+  }
+
+  @Test
+  public void restCallWithTraceHeader() throws Exception {
+    RestResponse response =
+        adminRestSession.putWithHeader(
+            "/projects/new4", new BasicHeader(RestApiServlet.X_GERRIT_TRACE, null));
+    assertThat(response.getStatusCode()).isEqualTo(SC_CREATED);
+    assertThat(response.getHeader(RestApiServlet.X_GERRIT_TRACE)).isNotNull();
+    assertThat(projectCreationListener.traceId).isNotNull();
+    assertThat(projectCreationListener.isLoggingForced).isTrue();
+  }
+
+  @Test
+  public void restCallWithTraceHeaderAndProvidedTraceId() throws Exception {
+    RestResponse response =
+        adminRestSession.putWithHeader(
+            "/projects/new5", new BasicHeader(RestApiServlet.X_GERRIT_TRACE, "issue/123"));
+    assertThat(response.getStatusCode()).isEqualTo(SC_CREATED);
+    assertThat(response.getHeader(RestApiServlet.X_GERRIT_TRACE)).isEqualTo("issue/123");
+    assertThat(projectCreationListener.traceId).isEqualTo("issue/123");
+    assertThat(projectCreationListener.isLoggingForced).isTrue();
+  }
+
+  @Test
+  public void restCallWithTraceRequestParamAndTraceHeader() throws Exception {
+    // trace ID only specified by trace header
+    RestResponse response =
+        adminRestSession.putWithHeader(
+            "/projects/new6?trace", new BasicHeader(RestApiServlet.X_GERRIT_TRACE, "issue/123"));
+    assertThat(response.getStatusCode()).isEqualTo(SC_CREATED);
+    assertThat(response.getHeader(RestApiServlet.X_GERRIT_TRACE)).isEqualTo("issue/123");
+    assertThat(projectCreationListener.traceId).isEqualTo("issue/123");
+    assertThat(projectCreationListener.isLoggingForced).isTrue();
+
+    // trace ID only specified by trace request parameter
+    response =
+        adminRestSession.putWithHeader(
+            "/projects/new7?trace=issue/123", new BasicHeader(RestApiServlet.X_GERRIT_TRACE, null));
+    assertThat(response.getStatusCode()).isEqualTo(SC_CREATED);
+    assertThat(response.getHeader(RestApiServlet.X_GERRIT_TRACE)).isEqualTo("issue/123");
+    assertThat(projectCreationListener.traceId).isEqualTo("issue/123");
+    assertThat(projectCreationListener.isLoggingForced).isTrue();
+
+    // same trace ID specified by trace header and trace request parameter
+    response =
+        adminRestSession.putWithHeader(
+            "/projects/new8?trace=issue/123",
+            new BasicHeader(RestApiServlet.X_GERRIT_TRACE, "issue/123"));
+    assertThat(response.getStatusCode()).isEqualTo(SC_CREATED);
+    assertThat(response.getHeader(RestApiServlet.X_GERRIT_TRACE)).isEqualTo("issue/123");
+    assertThat(projectCreationListener.traceId).isEqualTo("issue/123");
+    assertThat(projectCreationListener.isLoggingForced).isTrue();
+
+    // different trace IDs specified by trace header and trace request parameter
+    response =
+        adminRestSession.putWithHeader(
+            "/projects/new9?trace=issue/123",
+            new BasicHeader(RestApiServlet.X_GERRIT_TRACE, "issue/456"));
+    assertThat(response.getStatusCode()).isEqualTo(SC_CREATED);
+    assertThat(response.getHeaders(RestApiServlet.X_GERRIT_TRACE))
+        .containsExactly("issue/123", "issue/456");
+    assertThat(projectCreationListener.traceIds).containsExactly("issue/123", "issue/456");
     assertThat(projectCreationListener.isLoggingForced).isTrue();
   }
 
@@ -103,7 +166,6 @@
     PushOneCommit.Result r = push.to("refs/heads/master");
     r.assertOkStatus();
     assertThat(commitValidationListener.traceId).isNull();
-    assertThat(commitValidationListener.foundTraceId).isFalse();
     assertThat(commitValidationListener.isLoggingForced).isFalse();
   }
 
@@ -114,7 +176,6 @@
     PushOneCommit.Result r = push.to("refs/heads/master");
     r.assertOkStatus();
     assertThat(commitValidationListener.traceId).isNotNull();
-    assertThat(commitValidationListener.foundTraceId).isTrue();
     assertThat(commitValidationListener.isLoggingForced).isTrue();
   }
 
@@ -125,7 +186,6 @@
     PushOneCommit.Result r = push.to("refs/heads/master");
     r.assertOkStatus();
     assertThat(commitValidationListener.traceId).isEqualTo("issue/123");
-    assertThat(commitValidationListener.foundTraceId).isTrue();
     assertThat(commitValidationListener.isLoggingForced).isTrue();
   }
 
@@ -135,7 +195,6 @@
     PushOneCommit.Result r = push.to("refs/for/master");
     r.assertOkStatus();
     assertThat(commitValidationListener.traceId).isNull();
-    assertThat(commitValidationListener.foundTraceId).isFalse();
     assertThat(commitValidationListener.isLoggingForced).isFalse();
   }
 
@@ -146,7 +205,6 @@
     PushOneCommit.Result r = push.to("refs/for/master");
     r.assertOkStatus();
     assertThat(commitValidationListener.traceId).isNotNull();
-    assertThat(commitValidationListener.foundTraceId).isTrue();
     assertThat(commitValidationListener.isLoggingForced).isTrue();
   }
 
@@ -157,28 +215,26 @@
     PushOneCommit.Result r = push.to("refs/for/master");
     r.assertOkStatus();
     assertThat(commitValidationListener.traceId).isEqualTo("issue/123");
-    assertThat(commitValidationListener.foundTraceId).isTrue();
     assertThat(commitValidationListener.isLoggingForced).isTrue();
   }
 
   private static class TraceValidatingProjectCreationValidationListener
       implements ProjectCreationValidationListener {
     String traceId;
-    Boolean foundTraceId;
+    ImmutableSet<String> traceIds;
     Boolean isLoggingForced;
 
     @Override
     public void validateNewProject(CreateProjectArgs args) throws ValidationException {
       this.traceId =
           Iterables.getFirst(LoggingContext.getInstance().getTagsAsMap().get("TRACE_ID"), null);
-      this.foundTraceId = traceId != null;
+      this.traceIds = LoggingContext.getInstance().getTagsAsMap().get("TRACE_ID");
       this.isLoggingForced = LoggingContext.getInstance().shouldForceLogging(null, null, false);
     }
   }
 
   private static class TraceValidatingCommitValidationListener implements CommitValidationListener {
     String traceId;
-    Boolean foundTraceId;
     Boolean isLoggingForced;
 
     @Override
@@ -186,7 +242,6 @@
         throws CommitValidationException {
       this.traceId =
           Iterables.getFirst(LoggingContext.getInstance().getTagsAsMap().get("TRACE_ID"), null);
-      this.foundTraceId = traceId != null;
       this.isLoggingForced = LoggingContext.getInstance().shouldForceLogging(null, null, false);
       return ImmutableList.of();
     }