diff --git a/src/main/java/com/googlesource/gerrit/plugins/zuul/util/CommitMessageFetcher.java b/src/main/java/com/googlesource/gerrit/plugins/zuul/util/CommitMessageFetcher.java
index 8586be6..6bb2d4e 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/zuul/util/CommitMessageFetcher.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/zuul/util/CommitMessageFetcher.java
@@ -15,6 +15,8 @@
 package com.googlesource.gerrit.plugins.zuul.util;
 
 import com.google.gerrit.entities.Project;
+import com.google.gerrit.extensions.common.ChangeInfo;
+import com.google.gerrit.extensions.common.CommitInfo;
 import com.google.gerrit.server.git.GitRepositoryManager;
 import com.google.inject.Inject;
 import java.io.IOException;
@@ -40,4 +42,19 @@
       return commit.getFullMessage();
     }
   }
+
+  /**
+   * Extracts the commit message of the most current revision of a change.
+   *
+   * <p>The ChangeInfo must have the {@link CommitInfo} of at least the most current revision
+   * loaded.
+   *
+   * @param changeInfo The ChangeInfo to extract the commit message from
+   * @return the extracted commit message
+   */
+  public String fetch(ChangeInfo changeInfo) {
+    String current = changeInfo.currentRevision;
+    CommitInfo commitInfo = changeInfo.revisions.get(current).commit;
+    return commitInfo.message;
+  }
 }
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 1d75a60..aa772f1 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
@@ -13,8 +13,8 @@
 // limitations under the License.
 package com.googlesource.gerrit.plugins.zuul.util;
 
-import com.google.common.flogger.FluentLogger;
 import com.google.gerrit.entities.Change;
+import com.google.gerrit.extensions.client.ListChangesOption;
 import com.google.gerrit.extensions.common.ChangeInfo;
 import com.google.gerrit.extensions.restapi.AuthException;
 import com.google.gerrit.extensions.restapi.BadRequestException;
@@ -29,29 +29,42 @@
 
 /** Fetches the Needed-By part of cross repository dependencies. */
 public class NeededByFetcher {
-  private static final FluentLogger logger = FluentLogger.forEnclosingClass();
-
   private final ChangesCollection changes;
+  private final CommitMessageFetcher commitMessageFetcher;
+  private final DependsOnExtractor dependsOnExtractor;
 
   @Inject
-  public NeededByFetcher(ChangesCollection changes) {
+  public NeededByFetcher(
+      ChangesCollection changes,
+      CommitMessageFetcher commitMessageFetcher,
+      DependsOnExtractor dependsOnExtractor) {
     this.changes = changes;
+    this.commitMessageFetcher = commitMessageFetcher;
+    this.dependsOnExtractor = dependsOnExtractor;
   }
 
   public List<String> fetchForChangeKey(Change.Key key)
       throws BadRequestException, AuthException, PermissionBackendException {
+    String keyString = key.toString();
     List<String> neededBy = new ArrayList<>();
 
     QueryChanges query = changes.list();
-    String neededByQuery = "message:" + key + " -change:" + key;
+    String neededByQuery = "message:" + keyString + " -change:" + keyString;
+    query.addOption(ListChangesOption.CURRENT_REVISION);
+    query.addOption(ListChangesOption.CURRENT_COMMIT);
     query.addQuery(neededByQuery);
     Response<List<?>> response = query.apply(TopLevelResource.INSTANCE);
     @SuppressWarnings("unchecked")
     List<ChangeInfo> changes = (List<ChangeInfo>) response.value();
-    for (ChangeInfo other : changes) {
-      String otherKey = other.changeId;
-      logger.atFinest().log("Change %s needed by %s", key, otherKey);
-      neededBy.add(otherKey);
+    for (ChangeInfo changeInfo : changes) {
+      // The search found the key somewhere in the commit message. But this need not be a
+      // `Depends-On`. `key` might be mentioned for a completely different reason. So we need to
+      // check if `key` occurs in a `Depends-On`.
+      String commitMessage = commitMessageFetcher.fetch(changeInfo);
+      List<String> dependencies = dependsOnExtractor.extract(commitMessage);
+      if (dependencies.contains(keyString)) {
+        neededBy.add(changeInfo.changeId);
+      }
     }
     return neededBy;
   }
diff --git a/src/test/java/com/googlesource/gerrit/plugins/zuul/util/CommitMessageFetcherTest.java b/src/test/java/com/googlesource/gerrit/plugins/zuul/util/CommitMessageFetcherTest.java
index db228f3..905683c 100644
--- a/src/test/java/com/googlesource/gerrit/plugins/zuul/util/CommitMessageFetcherTest.java
+++ b/src/test/java/com/googlesource/gerrit/plugins/zuul/util/CommitMessageFetcherTest.java
@@ -21,9 +21,13 @@
 import static org.mockito.Mockito.when;
 
 import com.google.gerrit.entities.Project;
+import com.google.gerrit.extensions.common.ChangeInfo;
+import com.google.gerrit.extensions.common.CommitInfo;
+import com.google.gerrit.extensions.common.RevisionInfo;
 import com.google.gerrit.server.git.GitRepositoryManager;
 import java.io.IOException;
 import java.math.BigInteger;
+import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Set;
 import org.eclipse.jgit.errors.MissingObjectException;
@@ -84,6 +88,34 @@
     assertThat(commitMessage).isEqualTo("CommitMsg\n");
   }
 
+  @Test
+  public void testFetchChangeInfoSingleRevision() {
+    ChangeInfo changeInfo = new ChangeInfo();
+    changeInfo.currentRevision = "foo";
+    changeInfo.revisions = new HashMap<>();
+    changeInfo.revisions.put("foo", createRevisionInfo("CommitMsg"));
+
+    CommitMessageFetcher fetcher = createCommitMessageFetcher();
+    String commitMessage = fetcher.fetch(changeInfo);
+
+    assertThat(commitMessage).isEqualTo("CommitMsg");
+  }
+
+  @Test
+  public void testFetchChangeInfoMultipleRevisions() {
+    ChangeInfo changeInfo = new ChangeInfo();
+    changeInfo.currentRevision = "bar";
+    changeInfo.revisions = new HashMap<>();
+    changeInfo.revisions.put("foo", createRevisionInfo("CommitMsgFoo"));
+    changeInfo.revisions.put("bar", createRevisionInfo("CommitMsgBar"));
+    changeInfo.revisions.put("baz", createRevisionInfo("CommitMsgBaz"));
+
+    CommitMessageFetcher fetcher = createCommitMessageFetcher();
+    String commitMessage = fetcher.fetch(changeInfo);
+
+    assertThat(commitMessage).isEqualTo("CommitMsgBar");
+  }
+
   @Before
   public void setUp() throws Exception {
     ObjectLoader objectLoaderBlob = mock(ObjectLoader.class);
@@ -117,6 +149,16 @@
     when(repoManager.openRepository(eq(Project.nameKey("ProjectFoo")))).thenReturn(repo);
   }
 
+  private RevisionInfo createRevisionInfo(String commitMessage) {
+    CommitInfo commitInfo = new CommitInfo();
+    commitInfo.message = commitMessage;
+
+    RevisionInfo revisionInfo = new RevisionInfo();
+    revisionInfo.commit = commitInfo;
+
+    return revisionInfo;
+  }
+
   private CommitMessageFetcher createCommitMessageFetcher() {
     return new CommitMessageFetcher(repoManager);
   }
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 1d51857..51b90c8 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
@@ -14,11 +14,14 @@
 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.ArgumentMatchers.any;
 import static org.mockito.Mockito.doAnswer;
 import static org.mockito.Mockito.mock;
 import static org.mockito.Mockito.when;
 
 import com.google.gerrit.entities.Change;
+import com.google.gerrit.extensions.client.ListChangesOption;
 import com.google.gerrit.extensions.common.ChangeInfo;
 import com.google.gerrit.extensions.restapi.Response;
 import com.google.gerrit.extensions.restapi.TopLevelResource;
@@ -33,6 +36,8 @@
 
 public class NeededByFetcherTest {
   private ChangesCollection changes;
+  private CommitMessageFetcher commitMessageFetcher;
+  private DependsOnExtractor dependsOnExtractor;
   private Change.Key changeKey = getChangeKey(1);
 
   @Test
@@ -63,6 +68,38 @@
   }
 
   @Test
+  public void testFetchForChangeKeySingleResultUnmatchedEmpty() throws Exception {
+    List<ChangeInfo> searchResult = new ArrayList<>();
+    searchResult.add(getChangeInfo(2));
+
+    configureMocks(searchResult);
+    when(dependsOnExtractor.extract("commitMessage2")).thenReturn(new ArrayList<>());
+
+    NeededByFetcher fetcher = createFetcher();
+
+    List<String> neededBy = fetcher.fetchForChangeKey(changeKey);
+
+    assertThat(neededBy).isEmpty();
+  }
+
+  @Test
+  public void testFetchForChangeKeySingleResultUnmatchedDifferent() throws Exception {
+    List<ChangeInfo> searchResult = new ArrayList<>();
+    searchResult.add(getChangeInfo(2));
+
+    configureMocks(searchResult);
+    List<String> extracted = new ArrayList<>();
+    extracted.add(getChangeKey(3).toString());
+    when(dependsOnExtractor.extract("commitMessage2")).thenReturn(extracted);
+
+    NeededByFetcher fetcher = createFetcher();
+
+    List<String> neededBy = fetcher.fetchForChangeKey(changeKey);
+
+    assertThat(neededBy).isEmpty();
+  }
+
+  @Test
   public void testFetchForChangeKeyMultipleResults() throws Exception {
     List<ChangeInfo> searchResult = new ArrayList<>();
     searchResult.add(getChangeInfo(2));
@@ -77,18 +114,46 @@
     assertThat(neededBy).containsExactly(getChangeKey(2).toString(), getChangeKey(3).toString());
   }
 
+  @Test
+  public void testFetchForChangeKeyMultipleResultsSomeUnmatched() throws Exception {
+    List<ChangeInfo> searchResult = new ArrayList<>();
+    searchResult.add(getChangeInfo(2));
+    searchResult.add(getChangeInfo(3));
+    searchResult.add(getChangeInfo(4));
+    searchResult.add(getChangeInfo(5));
+
+    configureMocks(searchResult);
+    when(dependsOnExtractor.extract("commitMessage3")).thenReturn(new ArrayList<>());
+    when(dependsOnExtractor.extract("commitMessage4")).thenReturn(new ArrayList<>());
+
+    NeededByFetcher fetcher = createFetcher();
+
+    List<String> neededBy = fetcher.fetchForChangeKey(changeKey);
+
+    assertThat(neededBy).containsExactly(getChangeKey(2).toString(), getChangeKey(5).toString());
+  }
+
+  /**
+   * Sets up mocks for a given search result.
+   *
+   * <p>Each search result is configured to have a `Depends-On` to the changeKey per default. To
+   * refine, override the extraction for ("commitMessage" + number) to the desired list of
+   * Change-Ids.
+   *
+   * @param searchResult The search result to configure.
+   * @throws Exception thrown upon issues.
+   */
   public void configureMocks(final List<ChangeInfo> searchResult) throws Exception {
     QueryChanges queryChanges = mock(QueryChanges.class);
     final AtomicBoolean addedQuery = new AtomicBoolean(false);
-    doAnswer(
-            new Answer<Void>() {
-              @Override
-              public Void answer(InvocationOnMock invocation) throws Throwable {
-                addedQuery.getAndSet(true);
-                return null;
-              }
-            })
-        .when(queryChanges)
+    final AtomicBoolean addedOptionCurrentRevision = new AtomicBoolean(false);
+    final AtomicBoolean addedOptionCurrentCommit = new AtomicBoolean(false);
+
+    mockQueryChangesWithSwitch(queryChanges, addedOptionCurrentCommit)
+        .addOption(ListChangesOption.CURRENT_COMMIT);
+    mockQueryChangesWithSwitch(queryChanges, addedOptionCurrentRevision)
+        .addOption(ListChangesOption.CURRENT_REVISION);
+    mockQueryChangesWithSwitch(queryChanges, addedQuery)
         .addQuery("message:" + changeKey + " -change:" + changeKey);
     when(queryChanges.apply(TopLevelResource.INSTANCE))
         .thenAnswer(
@@ -97,12 +162,50 @@
               @Override
               public Response<List<ChangeInfo>> answer(InvocationOnMock invocation)
                   throws Throwable {
-                return Response.ok(addedQuery.get() ? searchResult : null);
+                boolean ready =
+                    addedOptionCurrentRevision.get()
+                        && addedOptionCurrentCommit.get()
+                        && addedQuery.get();
+                if (!ready) {
+                  fail("executed query before all options were set");
+                }
+                return Response.ok(searchResult);
               }
             });
 
     changes = mock(ChangesCollection.class);
     when(changes.list()).thenReturn(queryChanges);
+
+    commitMessageFetcher = mock(CommitMessageFetcher.class);
+    when(commitMessageFetcher.fetch(any(ChangeInfo.class)))
+        .thenAnswer(
+            new Answer<String>() {
+              @Override
+              public String answer(InvocationOnMock invocation) throws Throwable {
+                ChangeInfo changeInfo = invocation.getArgument(0);
+                return "commitMessage" + changeInfo._number;
+              }
+            });
+
+    dependsOnExtractor = mock(DependsOnExtractor.class);
+    List<String> extractedMatchList = new ArrayList<>();
+    extractedMatchList.add(changeKey.toString());
+    when(dependsOnExtractor.extract(any(String.class))).thenReturn(extractedMatchList);
+  }
+
+  private QueryChanges mockQueryChangesWithSwitch(
+      QueryChanges queryChanges, AtomicBoolean booleanSwitch) {
+    return doAnswer(
+            new Answer<Void>() {
+              @Override
+              public Void answer(InvocationOnMock invocation) throws Throwable {
+                if (booleanSwitch.getAndSet(true)) {
+                  fail("flag has already been set");
+                }
+                return null;
+              }
+            })
+        .when(queryChanges);
   }
 
   private Change.Key getChangeKey(int keyEnding) {
@@ -112,10 +215,11 @@
   private ChangeInfo getChangeInfo(int keyEnding) {
     ChangeInfo changeInfo = new ChangeInfo();
     changeInfo.changeId = getChangeKey(keyEnding).toString();
+    changeInfo._number = keyEnding;
     return changeInfo;
   }
 
   private NeededByFetcher createFetcher() {
-    return new NeededByFetcher(changes);
+    return new NeededByFetcher(changes, commitMessageFetcher, dependsOnExtractor);
   }
 }