diff --git a/java/com/google/gerrit/plugins/checks/api/ChecksFactory.java b/java/com/google/gerrit/plugins/checks/api/ChecksFactory.java
index 0ac45a9..ecd26d8 100644
--- a/java/com/google/gerrit/plugins/checks/api/ChecksFactory.java
+++ b/java/com/google/gerrit/plugins/checks/api/ChecksFactory.java
@@ -14,6 +14,8 @@
 
 package com.google.gerrit.plugins.checks.api;
 
+import com.google.gerrit.extensions.restapi.ResourceNotFoundException;
+import com.google.gerrit.extensions.restapi.RestApiException;
 import com.google.gerrit.reviewdb.client.Change;
 import com.google.gerrit.reviewdb.client.PatchSet;
 import com.google.gerrit.server.CurrentUser;
@@ -21,6 +23,7 @@
 import com.google.gerrit.server.change.ChangeResource;
 import com.google.gerrit.server.change.RevisionResource;
 import com.google.gerrit.server.notedb.ChangeNotes;
+import com.google.gerrit.server.project.NoSuchChangeException;
 import com.google.gwtorm.server.OrmException;
 import com.google.inject.Inject;
 import com.google.inject.Provider;
@@ -49,16 +52,30 @@
     this.changeResourceFactory = changeResourceFactory;
   }
 
-  public Checks currentRevision(Change.Id changeId) throws OrmException {
-    ChangeNotes notes = changeNotesFactory.createChecked(changeId);
-    return revision(notes.getChange().currentPatchSetId());
+  public Checks currentRevision(Change.Id changeId) throws OrmException, RestApiException {
+    ChangeResource changeResource = getChangeResource(changeId);
+    PatchSet patchSet = psUtil.current(changeResource.getNotes());
+    return getChecks(changeResource, patchSet);
   }
 
-  public Checks revision(PatchSet.Id patchSetId) throws OrmException {
-    ChangeNotes notes = changeNotesFactory.createChecked(patchSetId.getParentKey());
-    PatchSet patchSet = psUtil.get(notes, patchSetId);
-    RevisionResource revisionResource =
-        new RevisionResource(changeResourceFactory.create(notes, user.get()), patchSet);
+  public Checks revision(PatchSet.Id patchSetId) throws OrmException, RestApiException {
+    ChangeResource changeResource = getChangeResource(patchSetId.getParentKey());
+    PatchSet patchSet = psUtil.get(changeResource.getNotes(), patchSetId);
+    return getChecks(changeResource, patchSet);
+  }
+
+  private ChangeResource getChangeResource(Change.Id changeId)
+      throws OrmException, RestApiException {
+    try {
+      ChangeNotes notes = changeNotesFactory.createChecked(changeId);
+      return changeResourceFactory.create(notes, user.get());
+    } catch (NoSuchChangeException e) {
+      throw new ResourceNotFoundException(String.format("Change %d not found", changeId.get()), e);
+    }
+  }
+
+  private Checks getChecks(ChangeResource changeResource, PatchSet patchSet) {
+    RevisionResource revisionResource = new RevisionResource(changeResource, patchSet);
     return checksFactory.create(revisionResource);
   }
 }
diff --git a/javatests/com/google/gerrit/plugins/checks/acceptance/ChecksRefIT.java b/javatests/com/google/gerrit/plugins/checks/acceptance/ChecksRefIT.java
new file mode 100644
index 0000000..0482fae
--- /dev/null
+++ b/javatests/com/google/gerrit/plugins/checks/acceptance/ChecksRefIT.java
@@ -0,0 +1,50 @@
+// Copyright (C) 2019 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.plugins.checks.acceptance;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import com.google.gerrit.acceptance.testsuite.project.ProjectOperations;
+import com.google.gerrit.plugins.checks.CheckKey;
+import com.google.gerrit.plugins.checks.CheckerRef;
+import com.google.gerrit.plugins.checks.CheckerUuid;
+import com.google.gerrit.plugins.checks.api.CheckState;
+import com.google.gerrit.reviewdb.client.PatchSet;
+import com.google.inject.Inject;
+import org.junit.Before;
+import org.junit.Test;
+
+public class ChecksRefIT extends AbstractCheckersTest {
+  @Inject private ProjectOperations projectOperations;
+  private PatchSet.Id patchSetId;
+
+  @Before
+  public void setUp() throws Exception {
+    patchSetId = createChange().getPatchSetId();
+  }
+
+  @Test
+  public void noteDbRefOfCheckIsRemovedWhenChangeIsDeleted() throws Exception {
+    CheckerUuid checkerUuid = checkerOperations.newChecker().repository(project).create();
+    CheckKey checkKey = CheckKey.create(project, patchSetId, checkerUuid);
+    checkOperations.newCheck(checkKey).setState(CheckState.NOT_STARTED).upsert();
+    String noteDbChecksRef = CheckerRef.checksRef(patchSetId.getParentKey());
+    assertThat(projectOperations.project(project).hasHead(noteDbChecksRef)).isTrue();
+
+    gApi.changes().id(patchSetId.getParentKey().get()).delete();
+
+    assertThat(projectOperations.project(project).hasHead(noteDbChecksRef)).isFalse();
+  }
+}
diff --git a/javatests/com/google/gerrit/plugins/checks/acceptance/api/GetCheckIT.java b/javatests/com/google/gerrit/plugins/checks/acceptance/api/GetCheckIT.java
index 397b63b..2dff266 100644
--- a/javatests/com/google/gerrit/plugins/checks/acceptance/api/GetCheckIT.java
+++ b/javatests/com/google/gerrit/plugins/checks/acceptance/api/GetCheckIT.java
@@ -185,6 +185,25 @@
     assertThat(checkInfo).isEqualTo(checkOperations.check(checkKey).asInfo());
   }
 
+  @Test
+  public void checkForDeletedChangeDoesNotExist() throws Exception {
+    CheckerUuid checkerUuid = checkerOperations.newChecker().repository(project).create();
+    CheckKey checkKey = CheckKey.create(project, patchSetId, checkerUuid);
+    checkOperations.newCheck(checkKey).setState(CheckState.RUNNING).upsert();
+
+    gApi.changes().id(patchSetId.getParentKey().get()).delete();
+
+    try {
+      checksApiFactory.revision(patchSetId).id(checkerUuid).get();
+      assert_().fail("expected ResourceNotFoundException");
+    } catch (ResourceNotFoundException e) {
+      assertThat(e)
+          .hasMessageThat()
+          .ignoringCase()
+          .contains(String.format("change %d", patchSetId.getParentKey().get()));
+    }
+  }
+
   private Timestamp getPatchSetCreated(Change.Id changeId) throws RestApiException {
     return getOnlyElement(
             gApi.changes().id(changeId.get()).get(CURRENT_REVISION).revisions.values())