diff --git a/BUILD b/BUILD
index 5f1c689..39020c2 100644
--- a/BUILD
+++ b/BUILD
@@ -15,6 +15,7 @@
     name = "zuul",
     srcs = glob(["src/main/java/**/*.java"]),
     resources = glob(["src/main/**/*"]),
+    deps = ["@commons-lang3//jar"],
     manifest_entries = [
         "Gerrit-PluginName: zuul",
         "Gerrit-Module: com.googlesource.gerrit.plugins.zuul.Module",
@@ -39,6 +40,7 @@
     visibility = ["//visibility:public"],
     exports = PLUGIN_DEPS + PLUGIN_TEST_DEPS + [
         ":zuul__plugin",
+        "@commons-lang3//jar",
     ],
 )
 
diff --git a/gr-zuul/gr-zuul.js b/gr-zuul/gr-zuul.js
index 4afc62b..fe0c1f6 100644
--- a/gr-zuul/gr-zuul.js
+++ b/gr-zuul/gr-zuul.js
@@ -53,7 +53,8 @@
     return this.plugin.restApi().send('GET', url).then(crd => {
       this._crd = crd;
       this._crd_loaded = true;
-      this.setHidden(!(crd.depends_on.length || crd.needed_by.length));
+      this.setHidden(!(this._isDependsOnSectionVisible()
+                       || crd.needed_by.length));
     });
   }
 
@@ -68,8 +69,13 @@
     }
   }
 
-  _computeDependencyUrl(changeId) {
-    return Gerrit.Nav.getUrlForSearchQuery(changeId);
+  _computeDependencyUrl(changeInfo) {
+    return Gerrit.Nav.getUrlForSearchQuery(changeInfo.change_id);
+  }
+
+  _isDependsOnSectionVisible() {
+    return !!(this._crd.depends_on_found.length
+              + this._crd.depends_on_missing.length);
   }
 }
 
diff --git a/gr-zuul/gr-zuul_html.js b/gr-zuul/gr-zuul_html.js
index 6827042..e94376f 100644
--- a/gr-zuul/gr-zuul_html.js
+++ b/gr-zuul/gr-zuul_html.js
@@ -60,18 +60,21 @@
       .dependencyCycleDetected {
         color: #d17171;
       }
+      .missingFromThisServer {
+        color: #d17171;
+      }
     </style>
     <template is="dom-if" if="[[_crd_loaded]]">
-      <template is="dom-if" if="[[_crd.depends_on.length]]">
+      <template is="dom-if" if="[[_isDependsOnSectionVisible()]]">
         <section class="related-changes-section">
           <h4>Depends on</h4>
-          <template is="dom-repeat" items="[[_crd.depends_on]]">
+          <template is="dom-repeat" items="[[_crd.depends_on_found]]">
             <div class="changeContainer zuulDependencyContainer">
               <a
                 href$="[[_computeDependencyUrl(item)]]"
-                title$="[[item]]"
+                title$="[[item.project]]: [[item.branch]]: [[item.subject]]"
               >
-                [[item]]
+                [[item.project]]: [[item.branch]]: [[item.subject]]
               </a>
               <template is="dom-if" if="[[_crd.cycle]]">
                 <span class="status dependencyCycleDetected">
@@ -80,6 +83,16 @@
               </template>
             </div>
           </template>
+          <template is="dom-repeat" items="[[_crd.depends_on_missing]]">
+            <div class="changeContainer zuulDependencyContainer">
+              <span>
+                [[item]]
+              </span>
+              <span class="status missingFromThisServer">
+                (Missing from this server)
+              </span>
+            </div>
+          </template>
         </section>
       </template>
       <template is="dom-if" if="[[_crd.needed_by.length]]">
@@ -89,9 +102,9 @@
             <div class="changeContainer zuulDependencyContainer">
               <a
                 href$="[[_computeDependencyUrl(item)]]"
-                title$="[[item]]"
+                title$="[[item.project]]: [[item.branch]]: [[item.subject]]"
               >
-                [[item]]
+                [[item.project]]: [[item.branch]]: [[item.subject]]
               </a>
               <template is="dom-if" if="[[_crd.cycle]]">
                 <span class="status dependencyCycleDetected">
diff --git a/src/main/java/com/googlesource/gerrit/plugins/zuul/CrdInfo.java b/src/main/java/com/googlesource/gerrit/plugins/zuul/CrdInfo.java
index 3788684..84fbfa4 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/zuul/CrdInfo.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/zuul/CrdInfo.java
@@ -14,10 +14,20 @@
 
 package com.googlesource.gerrit.plugins.zuul;
 
+import com.google.gerrit.extensions.common.ChangeInfo;
 import java.util.List;
 
+/** Cross-repository dependencies of a Change */
 public class CrdInfo {
-  public List<String> dependsOn;
-  public List<String> neededBy;
+  /** Shallow ChangeInfos of changes that depend on this Change and are available on this server */
+  public List<ChangeInfo> dependsOnFound;
+
+  /** Change-Ids of changes that depend on this Change and are not available on this server */
+  public List<String> dependsOnMissing;
+
+  /** Shallow ChangeInfos of changes that depend on this Change */
+  public List<ChangeInfo> neededBy;
+
+  /** true, if this change is contained in a dependency cycle */
   public boolean cycle;
 }
diff --git a/src/main/java/com/googlesource/gerrit/plugins/zuul/GetCrd.java b/src/main/java/com/googlesource/gerrit/plugins/zuul/GetCrd.java
index 22b2f56..e536b2a 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/zuul/GetCrd.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/zuul/GetCrd.java
@@ -14,6 +14,7 @@
 
 package com.googlesource.gerrit.plugins.zuul;
 
+import com.google.gerrit.extensions.common.ChangeInfo;
 import com.google.gerrit.extensions.restapi.AuthException;
 import com.google.gerrit.extensions.restapi.BadRequestException;
 import com.google.gerrit.extensions.restapi.Response;
@@ -25,6 +26,10 @@
 import com.googlesource.gerrit.plugins.zuul.util.DependsOnFetcher;
 import com.googlesource.gerrit.plugins.zuul.util.NeededByFetcher;
 import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.stream.Collectors;
+import org.apache.commons.lang3.tuple.Pair;
 import org.eclipse.jgit.errors.RepositoryNotFoundException;
 
 @Singleton
@@ -43,14 +48,21 @@
       throws RepositoryNotFoundException, IOException, BadRequestException, AuthException,
           PermissionBackendException {
     CrdInfo out = new CrdInfo();
-
-    out.dependsOn = dependsOnFetcher.fetchForRevision(rsrc);
+    Pair<List<ChangeInfo>, List<String>> dependsOn = dependsOnFetcher.fetchForRevision(rsrc);
+    out.dependsOnFound = dependsOn.getLeft();
+    out.dependsOnMissing = dependsOn.getRight();
 
     out.neededBy = neededByFetcher.fetchForChangeKey(rsrc.getChange().getKey());
 
+    List<String> dependsOnAllKeys = new ArrayList<>(out.dependsOnMissing);
+    dependsOnAllKeys.addAll(
+        out.dependsOnFound.stream()
+            .map(changeInfo -> changeInfo.changeId)
+            .collect(Collectors.toList()));
+
     out.cycle = false;
-    for (String neededKey : out.neededBy) {
-      if (out.dependsOn.contains(neededKey)) {
+    for (ChangeInfo changeInfo : out.neededBy) {
+      if (dependsOnAllKeys.contains(changeInfo.changeId)) {
         out.cycle = true;
         break;
       }
diff --git a/src/main/java/com/googlesource/gerrit/plugins/zuul/util/DependsOnFetcher.java b/src/main/java/com/googlesource/gerrit/plugins/zuul/util/DependsOnFetcher.java
index ee66de0..0d599a1 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/zuul/util/DependsOnFetcher.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/zuul/util/DependsOnFetcher.java
@@ -13,30 +13,83 @@
 // limitations under the License.
 package com.googlesource.gerrit.plugins.zuul.util;
 
+import com.google.common.collect.Lists;
 import com.google.gerrit.entities.Project;
+import com.google.gerrit.extensions.common.ChangeInfo;
+import com.google.gerrit.extensions.restapi.AuthException;
+import com.google.gerrit.extensions.restapi.BadRequestException;
+import com.google.gerrit.extensions.restapi.Response;
+import com.google.gerrit.extensions.restapi.TopLevelResource;
 import com.google.gerrit.server.change.RevisionResource;
+import com.google.gerrit.server.permissions.PermissionBackendException;
+import com.google.gerrit.server.restapi.change.ChangesCollection;
+import com.google.gerrit.server.restapi.change.QueryChanges;
 import com.google.inject.Inject;
 import java.io.IOException;
+import java.util.ArrayList;
 import java.util.List;
+import org.apache.commons.lang3.tuple.ImmutablePair;
+import org.apache.commons.lang3.tuple.Pair;
 import org.eclipse.jgit.errors.RepositoryNotFoundException;
 
 /** Fetches the Depends-On part of cross repository dependencies. */
 public class DependsOnFetcher {
+  private final ChangesCollection changes;
   private final CommitMessageFetcher commitMessageFetcher;
   private final DependsOnExtractor dependsOnExtractor;
 
   @Inject
   public DependsOnFetcher(
-      CommitMessageFetcher commitMessageFetcher, DependsOnExtractor dependsOnExtractor) {
+      ChangesCollection changes,
+      CommitMessageFetcher commitMessageFetcher,
+      DependsOnExtractor dependsOnExtractor) {
+    this.changes = changes;
     this.commitMessageFetcher = commitMessageFetcher;
     this.dependsOnExtractor = dependsOnExtractor;
   }
 
-  public List<String> fetchForRevision(RevisionResource rsrc)
-      throws RepositoryNotFoundException, IOException {
+  @SuppressWarnings("unchecked")
+  private List<ChangeInfo> fetchChangeInfosForChangeKeys(List<String> keys)
+      throws BadRequestException, AuthException, PermissionBackendException {
+    List<ChangeInfo> ret;
+    if (keys.isEmpty()) {
+      ret = new ArrayList<>();
+    } else {
+      QueryChanges query = changes.list();
+      String queryString = "change:" + String.join(" OR change:", keys);
+      query.addQuery(queryString);
+      Response<List<?>> response = query.apply(TopLevelResource.INSTANCE);
+      ret = (List<ChangeInfo>) response.value();
+    }
+    return ret;
+  }
+
+  public Pair<List<ChangeInfo>, List<String>> fetchForRevision(RevisionResource rsrc)
+      throws RepositoryNotFoundException, IOException, BadRequestException, AuthException,
+          PermissionBackendException {
     Project.NameKey p = rsrc.getChange().getProject();
     String rev = rsrc.getPatchSet().commitId().getName();
     String commitMsg = commitMessageFetcher.fetch(p, rev);
-    return dependsOnExtractor.extract(commitMsg);
+
+    List<String> extractedChangeKeys = dependsOnExtractor.extract(commitMsg);
+    List<ChangeInfo> foundChangeInfos = fetchChangeInfosForChangeKeys(extractedChangeKeys);
+
+    // `extracted` and `found` need not agree in size. It might be that a Change-Id from
+    // `extracted` matches more than one Change (E.g.: cherry-picked to different branch). And it
+    // might be that a Change-Id from `extracted` does not yield a result.
+    // So we need to check that `found` holds at least one ChangeInfo for each Change-Id in
+    // `extractedDependsOn`.
+
+    List<String> resultMissing = Lists.newArrayList(extractedChangeKeys);
+    List<ChangeInfo> resultFound = new ArrayList<>(extractedChangeKeys.size());
+
+    for (ChangeInfo changeInfo : foundChangeInfos) {
+      String changeId = changeInfo.changeId.toString();
+      if (extractedChangeKeys.contains(changeId)) {
+        resultMissing.remove(changeId);
+        resultFound.add(changeInfo);
+      }
+    }
+    return new ImmutablePair<>(resultFound, resultMissing);
   }
 }
diff --git a/src/main/java/com/googlesource/gerrit/plugins/zuul/util/NeededByFetcher.java b/src/main/java/com/googlesource/gerrit/plugins/zuul/util/NeededByFetcher.java
index aa772f1..e11fd22 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/zuul/util/NeededByFetcher.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/zuul/util/NeededByFetcher.java
@@ -43,10 +43,10 @@
     this.dependsOnExtractor = dependsOnExtractor;
   }
 
-  public List<String> fetchForChangeKey(Change.Key key)
+  public List<ChangeInfo> fetchForChangeKey(Change.Key key)
       throws BadRequestException, AuthException, PermissionBackendException {
     String keyString = key.toString();
-    List<String> neededBy = new ArrayList<>();
+    List<ChangeInfo> neededBy = new ArrayList<>();
 
     QueryChanges query = changes.list();
     String neededByQuery = "message:" + keyString + " -change:" + keyString;
@@ -63,7 +63,7 @@
       String commitMessage = commitMessageFetcher.fetch(changeInfo);
       List<String> dependencies = dependsOnExtractor.extract(commitMessage);
       if (dependencies.contains(keyString)) {
-        neededBy.add(changeInfo.changeId);
+        neededBy.add(changeInfo);
       }
     }
     return neededBy;
diff --git a/src/main/resources/Documentation/rest-api-changes.md b/src/main/resources/Documentation/rest-api-changes.md
index ef348dd..9095d96 100644
--- a/src/main/resources/Documentation/rest-api-changes.md
+++ b/src/main/resources/Documentation/rest-api-changes.md
@@ -35,12 +35,25 @@
 
   )]}'
   {
-    "depends_on": [
-      "Ic79ed94daa9b58527139aadba1b0d59d1f54754b",
-      "I66853bf0c18e60f8de14d44dfb7c2ca1c3793111"
+    "depends_on_found": [
+      {
+        "id": "repo1~master~Ic0f5bcc8f998dfc0f1b7164de7a824f7832d4abe",
+        "project": "zuul/repo1",
+        "branch": "master",
+        [...]
+      }
+    ],
+    "depends_on_missing": [
+      "Ib01834990d3791330d65c469e9a3f93db6eb41f0",
+      "Ic0f5bcc8f998dfc0f1b7164de7a824f7832d4abe",
     ],
     "needed_by": [
-      "I66853bf0c18e60f8de14d44dfb7c2ca1c379311d"
+      {
+        "id": "another%2Frepo~master~I8944323ed34d55af7a17a48c8d8509f3cf62b6bf",
+        "project": "zuul/repo1",
+        "branch": "master",
+        [...]
+      }
     ],
     "cycle": false
   }
@@ -53,11 +66,12 @@
 
 The `CrdInfo` entity shows zuul dependencies on a patch set.
 
-|Field Name |Description|
-|:----------|:----------|
-|depends_on |List of changes that this change depends on|
-|needed_by  |List of changes that is dependent on this change|
-|cycle      |Whether this change is in a circular dependency chain|
+|Field Name         |Description|
+|:------------------|:----------|
+|depends_on_found   |List of shallow [ChangeInfo](../../../Documentation/rest-api-changes.html#change-info) entities. One for each Change that is available on this server and this change depends on|
+|depends_on_missing |List of Change-Ids. One for each change that is not available on this server although this change depends on|
+|needed_by          |List of shallow [ChangeInfo](../../../Documentation/rest-api-changes.html#change-info) entities. One for each change that is dependent on this change|
+|cycle              |Whether this change is in a circular dependency chain|
 
 
 SEE ALSO
diff --git a/src/test/java/com/googlesource/gerrit/plugins/zuul/GetCrdTest.java b/src/test/java/com/googlesource/gerrit/plugins/zuul/GetCrdTest.java
index d5a101e..71a46ee 100644
--- a/src/test/java/com/googlesource/gerrit/plugins/zuul/GetCrdTest.java
+++ b/src/test/java/com/googlesource/gerrit/plugins/zuul/GetCrdTest.java
@@ -18,152 +18,208 @@
 import static org.mockito.Mockito.when;
 
 import com.google.gerrit.entities.Change;
+import com.google.gerrit.extensions.common.ChangeInfo;
 import com.google.gerrit.extensions.restapi.Response;
 import com.google.gerrit.server.change.RevisionResource;
 import com.googlesource.gerrit.plugins.zuul.util.DependsOnFetcher;
 import com.googlesource.gerrit.plugins.zuul.util.NeededByFetcher;
 import java.util.ArrayList;
+import java.util.HashMap;
 import java.util.List;
+import java.util.Map;
+import org.apache.commons.lang3.tuple.ImmutablePair;
 import org.junit.Test;
 
 public class GetCrdTest {
   private RevisionResource rsrc;
   private DependsOnFetcher dependsOnFetcher;
   private NeededByFetcher neededByFetcher;
+  private Map<Integer, ChangeInfo> changeInfos = new HashMap<>();
 
   @Test
   public void testNoDependencies() throws Exception {
-    configureMocks(new ArrayList<>(), new ArrayList<>());
+    configureMocks(new ArrayList<>(), new ArrayList<>(), new ArrayList<>());
 
     GetCrd getCrd = createGetCrd();
     Response<CrdInfo> response = getCrd.apply(rsrc);
 
     assertThat(response.statusCode()).isEqualTo(200);
     CrdInfo crdInfo = response.value();
-    assertThat(crdInfo.dependsOn).isEmpty();
+    assertThat(crdInfo.dependsOnFound).isEmpty();
+    assertThat(crdInfo.dependsOnMissing).isEmpty();
     assertThat(crdInfo.neededBy).isEmpty();
     assertThat(crdInfo.cycle).isFalse();
   }
 
   @Test
-  public void testSingleDependsOn() throws Exception {
-    ArrayList<String> dependsOn = new ArrayList<>();
-    dependsOn.add("I00000000");
+  public void testSingleFoundDependsOn() throws Exception {
+    ArrayList<ChangeInfo> dependsOnFound = new ArrayList<>();
+    dependsOnFound.add(getChangeInfo(0));
 
-    configureMocks(dependsOn, new ArrayList<>());
+    configureMocks(dependsOnFound, new ArrayList<>(), new ArrayList<>());
 
     GetCrd getCrd = createGetCrd();
     Response<CrdInfo> response = getCrd.apply(rsrc);
 
     assertThat(response.statusCode()).isEqualTo(200);
     CrdInfo crdInfo = response.value();
-    assertThat(crdInfo.dependsOn).containsExactly("I00000000");
+    assertThat(crdInfo.dependsOnFound).containsExactly(getChangeInfo(0));
+    assertThat(crdInfo.dependsOnMissing).isEmpty();
     assertThat(crdInfo.neededBy).isEmpty();
     assertThat(crdInfo.cycle).isFalse();
   }
 
   @Test
-  public void testMultipleDependsOn() throws Exception {
-    ArrayList<String> dependsOn = new ArrayList<>();
-    dependsOn.add("I00000000");
-    dependsOn.add("I00000002");
-    dependsOn.add("I00000004");
+  public void testSingleMissingDependsOn() throws Exception {
+    ArrayList<String> dependsOnMissing = new ArrayList<>();
+    dependsOnMissing.add(getChangeKey(0));
 
-    configureMocks(dependsOn, new ArrayList<>());
+    configureMocks(new ArrayList<>(), dependsOnMissing, new ArrayList<>());
 
     GetCrd getCrd = createGetCrd();
     Response<CrdInfo> response = getCrd.apply(rsrc);
 
     assertThat(response.statusCode()).isEqualTo(200);
     CrdInfo crdInfo = response.value();
-    assertThat(crdInfo.dependsOn).containsExactly("I00000000", "I00000002", "I00000004");
+    assertThat(crdInfo.dependsOnFound).isEmpty();
+    assertThat(crdInfo.dependsOnMissing).containsExactly(getChangeKey(0));
+    assertThat(crdInfo.neededBy).isEmpty();
+    assertThat(crdInfo.cycle).isFalse();
+  }
+
+  @Test
+  public void testMultipleFoundDependsOn() throws Exception {
+    ArrayList<ChangeInfo> dependsOnFound = new ArrayList<>();
+    dependsOnFound.add(getChangeInfo(0));
+    dependsOnFound.add(getChangeInfo(2));
+    dependsOnFound.add(getChangeInfo(4));
+
+    configureMocks(dependsOnFound, new ArrayList<>(), new ArrayList<>());
+
+    GetCrd getCrd = createGetCrd();
+    Response<CrdInfo> response = getCrd.apply(rsrc);
+
+    assertThat(response.statusCode()).isEqualTo(200);
+    CrdInfo crdInfo = response.value();
+    assertThat(crdInfo.dependsOnFound)
+        .containsExactly(getChangeInfo(0), getChangeInfo(2), getChangeInfo(4));
+    assertThat(crdInfo.dependsOnMissing).isEmpty();
+    assertThat(crdInfo.neededBy).isEmpty();
+    assertThat(crdInfo.cycle).isFalse();
+  }
+
+  @Test
+  public void testMultipleMissingDependsOn() throws Exception {
+    ArrayList<String> dependsOnMissing = new ArrayList<>();
+    dependsOnMissing.add(getChangeKey(0));
+    dependsOnMissing.add(getChangeKey(2));
+    dependsOnMissing.add(getChangeKey(4));
+
+    configureMocks(new ArrayList<>(), dependsOnMissing, new ArrayList<>());
+
+    GetCrd getCrd = createGetCrd();
+    Response<CrdInfo> response = getCrd.apply(rsrc);
+
+    assertThat(response.statusCode()).isEqualTo(200);
+    CrdInfo crdInfo = response.value();
+    assertThat(crdInfo.dependsOnFound).isEmpty();
+    assertThat(crdInfo.dependsOnMissing)
+        .containsExactly(getChangeKey(0), getChangeKey(2), getChangeKey(4));
     assertThat(crdInfo.neededBy).isEmpty();
     assertThat(crdInfo.cycle).isFalse();
   }
 
   @Test
   public void testSingleNeededBy() throws Exception {
-    List<String> dependsOn = new ArrayList<>();
+    List<ChangeInfo> neededBy = new ArrayList<>();
+    neededBy.add(getChangeInfo(1));
 
-    List<String> neededBy = new ArrayList<>();
-    neededBy.add("I00000001");
-
-    configureMocks(dependsOn, neededBy);
+    configureMocks(new ArrayList<>(), new ArrayList<>(), neededBy);
 
     GetCrd getCrd = createGetCrd();
     Response<CrdInfo> response = getCrd.apply(rsrc);
 
     assertThat(response.statusCode()).isEqualTo(200);
     CrdInfo crdInfo = response.value();
-    assertThat(crdInfo.dependsOn).isEmpty();
-    assertThat(crdInfo.neededBy).containsExactly("I00000001");
+    assertThat(crdInfo.dependsOnFound).isEmpty();
+    assertThat(crdInfo.dependsOnMissing).isEmpty();
+    assertThat(crdInfo.neededBy).containsExactly(getChangeInfo(1));
     assertThat(crdInfo.cycle).isFalse();
   }
 
   @Test
   public void testMultipleNeededBy() throws Exception {
-    List<String> dependsOn = new ArrayList<>();
+    List<ChangeInfo> neededBy = new ArrayList<>();
+    neededBy.add(getChangeInfo(1));
+    neededBy.add(getChangeInfo(3));
+    neededBy.add(getChangeInfo(5));
 
-    List<String> neededBy = new ArrayList<>();
-    neededBy.add("I00000001");
-    neededBy.add("I00000003");
-    neededBy.add("I00000005");
-
-    configureMocks(dependsOn, neededBy);
+    configureMocks(new ArrayList<>(), new ArrayList<>(), neededBy);
 
     GetCrd getCrd = createGetCrd();
     Response<CrdInfo> response = getCrd.apply(rsrc);
 
     assertThat(response.statusCode()).isEqualTo(200);
     CrdInfo crdInfo = response.value();
-    assertThat(crdInfo.dependsOn).isEmpty();
-    assertThat(crdInfo.neededBy).containsExactly("I00000001", "I00000003", "I00000005");
+    assertThat(crdInfo.dependsOnFound).isEmpty();
+    assertThat(crdInfo.dependsOnMissing).isEmpty();
+    assertThat(crdInfo.neededBy)
+        .containsExactly(getChangeInfo(1), getChangeInfo(3), getChangeInfo(5));
     assertThat(crdInfo.cycle).isFalse();
   }
 
   @Test
   public void testMixed() throws Exception {
-    List<String> dependsOn = new ArrayList<>();
-    dependsOn.add("I00000002");
-    dependsOn.add("I00000004");
+    List<ChangeInfo> dependsOnFound = new ArrayList<>();
+    dependsOnFound.add(getChangeInfo(2));
+    dependsOnFound.add(getChangeInfo(4));
 
-    List<String> neededBy = new ArrayList<>();
-    neededBy.add("I00000001");
-    neededBy.add("I00000003");
+    List<String> dependsOnMissing = new ArrayList<>();
+    dependsOnMissing.add(getChangeKey(5));
+    dependsOnMissing.add(getChangeKey(6));
 
-    configureMocks(dependsOn, neededBy);
+    List<ChangeInfo> neededBy = new ArrayList<>();
+    neededBy.add(getChangeInfo(1));
+    neededBy.add(getChangeInfo(3));
+
+    configureMocks(dependsOnFound, dependsOnMissing, neededBy);
 
     GetCrd getCrd = createGetCrd();
     Response<CrdInfo> response = getCrd.apply(rsrc);
 
     assertThat(response.statusCode()).isEqualTo(200);
     CrdInfo crdInfo = response.value();
-    assertThat(crdInfo.dependsOn).containsExactly("I00000002", "I00000004");
-    assertThat(crdInfo.neededBy).containsExactly("I00000001", "I00000003");
+    assertThat(crdInfo.dependsOnFound).containsExactly(getChangeInfo(2), getChangeInfo(4));
+    assertThat(crdInfo.dependsOnMissing).containsExactly(getChangeKey(5), getChangeKey(6));
+    assertThat(crdInfo.neededBy).containsExactly(getChangeInfo(1), getChangeInfo(3));
     assertThat(crdInfo.cycle).isFalse();
   }
 
   @Test
   public void testSimpleCycle() throws Exception {
-    List<String> dependsOn = new ArrayList<>();
-    dependsOn.add("I00000001");
+    List<ChangeInfo> dependsOn = new ArrayList<>();
+    dependsOn.add(getChangeInfo(1));
 
-    List<String> neededBy = new ArrayList<>();
-    neededBy.add("I00000001");
+    List<ChangeInfo> neededBy = new ArrayList<>();
+    neededBy.add(getChangeInfo(1));
 
-    configureMocks(dependsOn, neededBy);
+    configureMocks(dependsOn, new ArrayList<>(), neededBy);
 
     GetCrd getCrd = createGetCrd();
     Response<CrdInfo> response = getCrd.apply(rsrc);
 
     assertThat(response.statusCode()).isEqualTo(200);
     CrdInfo crdInfo = response.value();
-    assertThat(crdInfo.dependsOn).containsExactly("I00000001");
-    assertThat(crdInfo.neededBy).containsExactly("I00000001");
+    assertThat(crdInfo.dependsOnFound).containsExactly(getChangeInfo(1));
+    assertThat(crdInfo.dependsOnMissing).isEmpty();
+    assertThat(crdInfo.neededBy).containsExactly(getChangeInfo(1));
     assertThat(crdInfo.cycle).isTrue();
   }
 
-  public void configureMocks(final List<String> dependsOn, final List<String> neededBy)
+  public void configureMocks(
+      final List<ChangeInfo> dependsOnFound,
+      final List<String> dependsOnMissing,
+      final List<ChangeInfo> neededBy)
       throws Exception {
     Change.Key changeKey = Change.key("I0123456789");
     Change change = new Change(changeKey, null, null, null, null);
@@ -171,12 +227,28 @@
     when(rsrc.getChange()).thenReturn(change);
 
     dependsOnFetcher = mock(DependsOnFetcher.class);
-    when(dependsOnFetcher.fetchForRevision(rsrc)).thenReturn(dependsOn);
+    when(dependsOnFetcher.fetchForRevision(rsrc))
+        .thenReturn(new ImmutablePair<>(dependsOnFound, dependsOnMissing));
 
     neededByFetcher = mock(NeededByFetcher.class);
     when(neededByFetcher.fetchForChangeKey(changeKey)).thenReturn(neededBy);
   }
 
+  private String getChangeKey(int keyEnding) {
+    return "I0123456789abcdef0000000000000000000" + (10000 + keyEnding);
+  }
+
+  private ChangeInfo getChangeInfo(int keyEnding) {
+    return changeInfos.computeIfAbsent(
+        keyEnding,
+        neededKeyEnding -> {
+          ChangeInfo changeInfo = new ChangeInfo();
+          changeInfo.changeId = getChangeKey(neededKeyEnding);
+          changeInfo._number = neededKeyEnding;
+          return changeInfo;
+        });
+  }
+
   private GetCrd createGetCrd() {
     return new GetCrd(dependsOnFetcher, neededByFetcher);
   }
diff --git a/src/test/java/com/googlesource/gerrit/plugins/zuul/util/DependsOnFetcherTest.java b/src/test/java/com/googlesource/gerrit/plugins/zuul/util/DependsOnFetcherTest.java
index 3cc6652..75247df 100644
--- a/src/test/java/com/googlesource/gerrit/plugins/zuul/util/DependsOnFetcherTest.java
+++ b/src/test/java/com/googlesource/gerrit/plugins/zuul/util/DependsOnFetcherTest.java
@@ -14,6 +14,8 @@
 package com.googlesource.gerrit.plugins.zuul.util;
 
 import static com.google.common.truth.Truth.assertThat;
+import static org.junit.Assert.fail;
+import static org.mockito.Mockito.doAnswer;
 import static org.mockito.Mockito.mock;
 import static org.mockito.Mockito.when;
 
@@ -21,57 +23,168 @@
 import com.google.gerrit.entities.Change;
 import com.google.gerrit.entities.PatchSet;
 import com.google.gerrit.entities.Project;
+import com.google.gerrit.extensions.common.ChangeInfo;
+import com.google.gerrit.extensions.restapi.AuthException;
+import com.google.gerrit.extensions.restapi.BadRequestException;
+import com.google.gerrit.extensions.restapi.Response;
+import com.google.gerrit.extensions.restapi.TopLevelResource;
 import com.google.gerrit.server.change.RevisionResource;
+import com.google.gerrit.server.permissions.PermissionBackendException;
+import com.google.gerrit.server.restapi.change.ChangesCollection;
+import com.google.gerrit.server.restapi.change.QueryChanges;
 import java.io.IOException;
 import java.util.ArrayList;
+import java.util.HashMap;
 import java.util.List;
+import java.util.Map;
+import java.util.concurrent.atomic.AtomicBoolean;
+import org.apache.commons.lang3.tuple.Pair;
 import org.eclipse.jgit.errors.RepositoryNotFoundException;
 import org.eclipse.jgit.lib.ObjectId;
 import org.junit.Test;
+import org.mockito.invocation.InvocationOnMock;
+import org.mockito.stubbing.Answer;
 
 public class DependsOnFetcherTest {
+  private ChangesCollection changes;
   private CommitMessageFetcher commitMessageFetcher;
   private DependsOnExtractor dependsOnExtractor;
   private RevisionResource rsrc;
+  private Map<Integer, ChangeInfo> changeInfos = new HashMap<>();
 
   @Test
   public void testExtractNoDependencies() throws Exception {
-    configureMocks(new ArrayList<>());
+    configureMocks(new ArrayList<>(), new ArrayList<>());
 
     DependsOnFetcher fetcher = createFetcher();
-    List<String> dependsOn = fetcher.fetchForRevision(rsrc);
+    Pair<List<ChangeInfo>, List<String>> dependsOn = fetcher.fetchForRevision(rsrc);
 
-    assertThat(dependsOn).isEmpty();
+    assertThat(dependsOn.getLeft()).isEmpty();
+    assertThat(dependsOn.getRight()).isEmpty();
   }
 
   @Test
-  public void testExtractSingleDependency() throws Exception {
+  public void testExtractSingleFoundDependency() throws Exception {
     List<String> extracted = new ArrayList<>();
-    extracted.add("I00000001");
-    configureMocks(extracted);
+    extracted.add(getChangeKey(1));
+
+    List<ChangeInfo> searchResult = new ArrayList<>();
+    searchResult.add(getChangeInfo(1));
+    configureMocks(extracted, searchResult);
 
     DependsOnFetcher fetcher = createFetcher();
-    List<String> dependsOn = fetcher.fetchForRevision(rsrc);
+    Pair<List<ChangeInfo>, List<String>> dependsOn = fetcher.fetchForRevision(rsrc);
 
-    assertThat(dependsOn).containsExactly("I00000001");
+    assertThat(dependsOn.getLeft()).containsExactly(getChangeInfo(1));
+    assertThat(dependsOn.getRight()).isEmpty();
   }
 
   @Test
-  public void testExtractMultipleDependencies() throws Exception {
+  public void testExtractMultipleFoundDependencies() throws Exception {
     List<String> extracted = new ArrayList<>();
-    extracted.add("I00000001");
-    extracted.add("I00000002");
-    extracted.add("I00000003");
-    configureMocks(extracted);
+    extracted.add(getChangeKey(1));
+    extracted.add(getChangeKey(2));
+    extracted.add(getChangeKey(3));
+    List<ChangeInfo> searchResult = new ArrayList<>();
+    searchResult.add(getChangeInfo(1));
+    searchResult.add(getChangeInfo(2));
+    searchResult.add(getChangeInfo(3));
+    configureMocks(extracted, searchResult);
 
     DependsOnFetcher fetcher = createFetcher();
-    List<String> dependsOn = fetcher.fetchForRevision(rsrc);
+    Pair<List<ChangeInfo>, List<String>> dependsOn = fetcher.fetchForRevision(rsrc);
 
-    assertThat(dependsOn).containsExactly("I00000001", "I00000002", "I00000003");
+    assertThat(dependsOn.getLeft())
+        .containsExactly(getChangeInfo(1), getChangeInfo(2), getChangeInfo(3));
+    assertThat(dependsOn.getRight()).isEmpty();
   }
 
-  private void configureMocks(List<String> dependsOn)
-      throws RepositoryNotFoundException, IOException {
+  @Test
+  public void testExtractSingleMissingDependency() throws Exception {
+    List<String> extracted = new ArrayList<>();
+    extracted.add(getChangeKey(1));
+
+    configureMocks(extracted, new ArrayList<>());
+
+    DependsOnFetcher fetcher = createFetcher();
+    Pair<List<ChangeInfo>, List<String>> dependsOn = fetcher.fetchForRevision(rsrc);
+
+    assertThat(dependsOn.getLeft()).isEmpty();
+    assertThat(dependsOn.getRight()).containsExactly(getChangeKey(1));
+  }
+
+  @Test
+  public void testExtractMultipleMissingDependencies() throws Exception {
+    List<String> extracted = new ArrayList<>();
+    extracted.add(getChangeKey(1));
+    extracted.add(getChangeKey(2));
+    extracted.add(getChangeKey(3));
+    configureMocks(extracted, new ArrayList<>());
+
+    DependsOnFetcher fetcher = createFetcher();
+    Pair<List<ChangeInfo>, List<String>> dependsOn = fetcher.fetchForRevision(rsrc);
+
+    assertThat(dependsOn.getLeft()).isEmpty();
+    assertThat(dependsOn.getRight())
+        .containsExactly(getChangeKey(1), getChangeKey(2), getChangeKey(3));
+  }
+
+  @Test
+  public void testExtractMultipleDependenciesMultipleResultsForChangeId() throws Exception {
+    List<String> extracted = new ArrayList<>();
+    extracted.add(getChangeKey(1));
+    extracted.add(getChangeKey(2));
+    extracted.add(getChangeKey(3));
+
+    List<ChangeInfo> searchResult = new ArrayList<>();
+    searchResult.add(getChangeInfo(1));
+    searchResult.add(getChangeInfo(2));
+    searchResult.add(getChangeInfo(3));
+
+    ChangeInfo changeInfo = getChangeInfo(102);
+    changeInfo.changeId = getChangeInfo(2).changeId;
+    searchResult.add(changeInfo);
+
+    configureMocks(extracted, searchResult);
+
+    DependsOnFetcher fetcher = createFetcher();
+    Pair<List<ChangeInfo>, List<String>> dependsOn = fetcher.fetchForRevision(rsrc);
+
+    assertThat(dependsOn.getLeft())
+        .containsExactly(getChangeInfo(1), getChangeInfo(2), getChangeInfo(3), getChangeInfo(102));
+    assertThat(dependsOn.getRight()).isEmpty();
+  }
+
+  @Test
+  public void testExtractMixed() throws Exception {
+    List<String> extracted = new ArrayList<>();
+    extracted.add(getChangeKey(1));
+    extracted.add(getChangeKey(2));
+    extracted.add(getChangeKey(3));
+    extracted.add(getChangeKey(4));
+
+    List<ChangeInfo> searchResult = new ArrayList<>();
+    searchResult.add(getChangeInfo(2));
+    searchResult.add(getChangeInfo(3));
+
+    ChangeInfo changeInfo = getChangeInfo(102);
+    changeInfo.changeId = getChangeInfo(2).changeId;
+    searchResult.add(changeInfo);
+
+    configureMocks(extracted, searchResult);
+
+    DependsOnFetcher fetcher = createFetcher();
+    Pair<List<ChangeInfo>, List<String>> dependsOn = fetcher.fetchForRevision(rsrc);
+
+    assertThat(dependsOn.getLeft())
+        .containsExactly(getChangeInfo(2), getChangeInfo(102), getChangeInfo(3));
+    assertThat(dependsOn.getRight()).containsExactly(getChangeKey(1), getChangeKey(4));
+  }
+
+  private void configureMocks(
+      List<String> extractedDependsOn, List<ChangeInfo> searchResultDependsOn)
+      throws RepositoryNotFoundException, IOException, BadRequestException, AuthException,
+          PermissionBackendException {
     String commitId = "0123456789012345678901234567890123456789";
 
     Project.NameKey projectNameKey = Project.nameKey("projectFoo");
@@ -92,10 +205,60 @@
     when(commitMessageFetcher.fetch(projectNameKey, commitId)).thenReturn("commitMsgFoo");
 
     dependsOnExtractor = mock(DependsOnExtractor.class);
-    when(dependsOnExtractor.extract("commitMsgFoo")).thenReturn(dependsOn);
+    when(dependsOnExtractor.extract("commitMsgFoo")).thenReturn(extractedDependsOn);
+
+    QueryChanges queryChanges = mock(QueryChanges.class);
+    final AtomicBoolean addedQuery = new AtomicBoolean(false);
+
+    if (!extractedDependsOn.isEmpty()) {
+      doAnswer(
+              new Answer<Void>() {
+                @Override
+                public Void answer(InvocationOnMock invocation) throws Throwable {
+                  if (addedQuery.getAndSet(true)) {
+                    fail("flag has already been set");
+                  }
+                  return null;
+                }
+              })
+          .when(queryChanges)
+          .addQuery("change:" + String.join(" OR change:", extractedDependsOn));
+
+      when(queryChanges.apply(TopLevelResource.INSTANCE))
+          .thenAnswer(
+              new Answer<Response<List<ChangeInfo>>>() {
+
+                @Override
+                public Response<List<ChangeInfo>> answer(InvocationOnMock invocation)
+                    throws Throwable {
+                  if (!addedQuery.get()) {
+                    fail("executed query before all options were set");
+                  }
+                  return Response.ok(searchResultDependsOn);
+                }
+              });
+    }
+
+    changes = mock(ChangesCollection.class);
+    when(changes.list()).thenReturn(queryChanges);
+  }
+
+  private String getChangeKey(int keyEnding) {
+    return "I0123456789abcdef0000000000000000000" + (10000 + keyEnding);
+  }
+
+  private ChangeInfo getChangeInfo(int keyEnding) {
+    return changeInfos.computeIfAbsent(
+        keyEnding,
+        neededKeyEnding -> {
+          ChangeInfo changeInfo = new ChangeInfo();
+          changeInfo.changeId = getChangeKey(neededKeyEnding);
+          changeInfo._number = neededKeyEnding;
+          return changeInfo;
+        });
   }
 
   private DependsOnFetcher createFetcher() {
-    return new DependsOnFetcher(commitMessageFetcher, dependsOnExtractor);
+    return new DependsOnFetcher(changes, commitMessageFetcher, dependsOnExtractor);
   }
 }
diff --git a/src/test/java/com/googlesource/gerrit/plugins/zuul/util/NeededByFetcherTest.java b/src/test/java/com/googlesource/gerrit/plugins/zuul/util/NeededByFetcherTest.java
index 51b90c8..69c6977 100644
--- a/src/test/java/com/googlesource/gerrit/plugins/zuul/util/NeededByFetcherTest.java
+++ b/src/test/java/com/googlesource/gerrit/plugins/zuul/util/NeededByFetcherTest.java
@@ -28,7 +28,9 @@
 import com.google.gerrit.server.restapi.change.ChangesCollection;
 import com.google.gerrit.server.restapi.change.QueryChanges;
 import java.util.ArrayList;
+import java.util.HashMap;
 import java.util.List;
+import java.util.Map;
 import java.util.concurrent.atomic.AtomicBoolean;
 import org.junit.Test;
 import org.mockito.invocation.InvocationOnMock;
@@ -39,6 +41,7 @@
   private CommitMessageFetcher commitMessageFetcher;
   private DependsOnExtractor dependsOnExtractor;
   private Change.Key changeKey = getChangeKey(1);
+  private Map<Integer, ChangeInfo> changeInfos = new HashMap<>();
 
   @Test
   public void testFetchForChangeKeyNoResults() throws Exception {
@@ -48,7 +51,7 @@
 
     NeededByFetcher fetcher = createFetcher();
 
-    List<String> neededBy = fetcher.fetchForChangeKey(changeKey);
+    List<ChangeInfo> neededBy = fetcher.fetchForChangeKey(changeKey);
 
     assertThat(neededBy).isEmpty();
   }
@@ -62,9 +65,9 @@
 
     NeededByFetcher fetcher = createFetcher();
 
-    List<String> neededBy = fetcher.fetchForChangeKey(changeKey);
+    List<ChangeInfo> neededBy = fetcher.fetchForChangeKey(changeKey);
 
-    assertThat(neededBy).containsExactly(getChangeKey(2).toString());
+    assertThat(neededBy).containsExactly(getChangeInfo(2));
   }
 
   @Test
@@ -77,7 +80,7 @@
 
     NeededByFetcher fetcher = createFetcher();
 
-    List<String> neededBy = fetcher.fetchForChangeKey(changeKey);
+    List<ChangeInfo> neededBy = fetcher.fetchForChangeKey(changeKey);
 
     assertThat(neededBy).isEmpty();
   }
@@ -94,7 +97,7 @@
 
     NeededByFetcher fetcher = createFetcher();
 
-    List<String> neededBy = fetcher.fetchForChangeKey(changeKey);
+    List<ChangeInfo> neededBy = fetcher.fetchForChangeKey(changeKey);
 
     assertThat(neededBy).isEmpty();
   }
@@ -109,9 +112,9 @@
 
     NeededByFetcher fetcher = createFetcher();
 
-    List<String> neededBy = fetcher.fetchForChangeKey(changeKey);
+    List<ChangeInfo> neededBy = fetcher.fetchForChangeKey(changeKey);
 
-    assertThat(neededBy).containsExactly(getChangeKey(2).toString(), getChangeKey(3).toString());
+    assertThat(neededBy).containsExactly(getChangeInfo(2), getChangeInfo(3));
   }
 
   @Test
@@ -128,9 +131,9 @@
 
     NeededByFetcher fetcher = createFetcher();
 
-    List<String> neededBy = fetcher.fetchForChangeKey(changeKey);
+    List<ChangeInfo> neededBy = fetcher.fetchForChangeKey(changeKey);
 
-    assertThat(neededBy).containsExactly(getChangeKey(2).toString(), getChangeKey(5).toString());
+    assertThat(neededBy).containsExactly(getChangeInfo(2), getChangeInfo(5));
   }
 
   /**
@@ -213,10 +216,14 @@
   }
 
   private ChangeInfo getChangeInfo(int keyEnding) {
-    ChangeInfo changeInfo = new ChangeInfo();
-    changeInfo.changeId = getChangeKey(keyEnding).toString();
-    changeInfo._number = keyEnding;
-    return changeInfo;
+    return changeInfos.computeIfAbsent(
+        keyEnding,
+        neededKeyEnding -> {
+          ChangeInfo changeInfo = new ChangeInfo();
+          changeInfo.changeId = getChangeKey(neededKeyEnding).toString();
+          changeInfo._number = neededKeyEnding;
+          return changeInfo;
+        });
   }
 
   private NeededByFetcher createFetcher() {