diff --git a/src/main/java/com/googlesource/gerrit/plugins/deleteproject/DeleteAction.java b/src/main/java/com/googlesource/gerrit/plugins/deleteproject/DeleteAction.java
index d9f427c..459d819 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/deleteproject/DeleteAction.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/deleteproject/DeleteAction.java
@@ -20,6 +20,7 @@
 import com.google.inject.Inject;
 import com.google.inject.Provider;
 import com.googlesource.gerrit.plugins.deleteproject.cache.CacheDeleteHandler;
+import com.googlesource.gerrit.plugins.deleteproject.database.DatabaseDeleteHandler;
 import com.googlesource.gerrit.plugins.deleteproject.fs.FilesystemDeleteHandler;
 
 public class DeleteAction extends DeleteProject implements UiAction<ProjectResource> {
@@ -28,6 +29,7 @@
   @Inject
   DeleteAction(
       ProtectedProjects protectedProjects,
+      DatabaseDeleteHandler dbHandler,
       FilesystemDeleteHandler fsHandler,
       CacheDeleteHandler cacheHandler,
       Provider<CurrentUser> userProvider,
@@ -35,7 +37,15 @@
       DeletePreconditions preConditions,
       Configuration cfg,
       HideProject hideProject) {
-    super(fsHandler, cacheHandler, userProvider, deleteLog, preConditions, cfg, hideProject);
+    super(
+        dbHandler,
+        fsHandler,
+        cacheHandler,
+        userProvider,
+        deleteLog,
+        preConditions,
+        cfg,
+        hideProject);
     this.protectedProjects = protectedProjects;
   }
 
diff --git a/src/main/java/com/googlesource/gerrit/plugins/deleteproject/DeleteProject.java b/src/main/java/com/googlesource/gerrit/plugins/deleteproject/DeleteProject.java
index b1de7fa..f8e4c2b 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/deleteproject/DeleteProject.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/deleteproject/DeleteProject.java
@@ -27,6 +27,7 @@
 import com.google.inject.Singleton;
 import com.googlesource.gerrit.plugins.deleteproject.DeleteProject.Input;
 import com.googlesource.gerrit.plugins.deleteproject.cache.CacheDeleteHandler;
+import com.googlesource.gerrit.plugins.deleteproject.database.DatabaseDeleteHandler;
 import com.googlesource.gerrit.plugins.deleteproject.fs.FilesystemDeleteHandler;
 import java.io.IOException;
 import org.eclipse.jgit.errors.RepositoryNotFoundException;
@@ -40,6 +41,7 @@
 
   protected final DeletePreconditions preConditions;
 
+  private final DatabaseDeleteHandler dbHandler;
   private final FilesystemDeleteHandler fsHandler;
   private final CacheDeleteHandler cacheHandler;
   private final Provider<CurrentUser> userProvider;
@@ -49,6 +51,7 @@
 
   @Inject
   DeleteProject(
+      DatabaseDeleteHandler dbHandler,
       FilesystemDeleteHandler fsHandler,
       CacheDeleteHandler cacheHandler,
       Provider<CurrentUser> userProvider,
@@ -56,6 +59,7 @@
       DeletePreconditions preConditions,
       Configuration cfg,
       HideProject hideProject) {
+    this.dbHandler = dbHandler;
     this.fsHandler = fsHandler;
     this.cacheHandler = cacheHandler;
     this.userProvider = userProvider;
@@ -80,6 +84,7 @@
     Exception ex = null;
     try {
       if (!preserve || !cfg.projectOnPreserveHidden()) {
+        dbHandler.delete(project);
         try {
           fsHandler.delete(project, preserve);
         } catch (RepositoryNotFoundException e) {
diff --git a/src/main/java/com/googlesource/gerrit/plugins/deleteproject/database/DatabaseDeleteHandler.java b/src/main/java/com/googlesource/gerrit/plugins/deleteproject/database/DatabaseDeleteHandler.java
new file mode 100644
index 0000000..9ee3cbb
--- /dev/null
+++ b/src/main/java/com/googlesource/gerrit/plugins/deleteproject/database/DatabaseDeleteHandler.java
@@ -0,0 +1,121 @@
+// Copyright (C) 2013 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.googlesource.gerrit.plugins.deleteproject.database;
+
+import static java.util.Collections.singleton;
+import static java.util.stream.Collectors.toList;
+
+import com.google.common.flogger.FluentLogger;
+import com.google.gerrit.entities.Account;
+import com.google.gerrit.entities.Change;
+import com.google.gerrit.entities.Project;
+import com.google.gerrit.server.StarredChangesUtil;
+import com.google.gerrit.server.UserInitiated;
+import com.google.gerrit.server.account.AccountState;
+import com.google.gerrit.server.account.AccountsUpdate;
+import com.google.gerrit.server.account.ProjectWatches.ProjectWatchKey;
+import com.google.gerrit.server.git.GitRepositoryManager;
+import com.google.gerrit.server.index.change.ChangeIndexer;
+import com.google.gerrit.server.notedb.ChangeNotes;
+import com.google.gerrit.server.notedb.ChangeNotes.Factory.ChangeNotesResult;
+import com.google.gerrit.server.project.NoSuchChangeException;
+import com.google.gerrit.server.query.account.InternalAccountQuery;
+import com.google.inject.Inject;
+import com.google.inject.Provider;
+import java.io.IOException;
+import java.util.List;
+import org.eclipse.jgit.errors.ConfigInvalidException;
+
+public class DatabaseDeleteHandler {
+  private static final FluentLogger log = FluentLogger.forEnclosingClass();
+
+  private final StarredChangesUtil starredChangesUtil;
+  private final ChangeIndexer indexer;
+  private final Provider<InternalAccountQuery> accountQueryProvider;
+  private final Provider<AccountsUpdate> accountsUpdateProvider;
+  private final ChangeNotes.Factory schemaFactoryNoteDb;
+  private final GitRepositoryManager repoManager;
+
+  @Inject
+  public DatabaseDeleteHandler(
+      StarredChangesUtil starredChangesUtil,
+      ChangeIndexer indexer,
+      ChangeNotes.Factory schemaFactoryNoteDb,
+      GitRepositoryManager repoManager,
+      Provider<InternalAccountQuery> accountQueryProvider,
+      @UserInitiated Provider<AccountsUpdate> accountsUpdateProvider) {
+    this.starredChangesUtil = starredChangesUtil;
+    this.indexer = indexer;
+    this.accountQueryProvider = accountQueryProvider;
+    this.accountsUpdateProvider = accountsUpdateProvider;
+    this.schemaFactoryNoteDb = schemaFactoryNoteDb;
+    this.repoManager = repoManager;
+  }
+
+  public void delete(Project project) throws IOException {
+    atomicDelete(project, getChangesListFromNoteDb(project));
+  }
+
+  private List<Change.Id> getChangesListFromNoteDb(Project project) throws IOException {
+    Project.NameKey projectKey = project.getNameKey();
+    List<Change.Id> changeIds =
+        schemaFactoryNoteDb
+            .scan(repoManager.openRepository(projectKey), projectKey)
+            .map(ChangeNotesResult::id)
+            .collect(toList());
+    log.atFine().log(
+        "Number of changes in noteDb related to project %s are %d",
+        projectKey.get(), changeIds.size());
+    return changeIds;
+  }
+
+  private void deleteChanges(List<Change.Id> changeIds) {
+
+    for (Change.Id id : changeIds) {
+      try {
+        starredChangesUtil.unstarAllForChangeDeletion(id);
+      } catch (NoSuchChangeException | IOException e) {
+        // we can ignore the exception during delete
+      }
+      // Delete from the secondary index
+      indexer.delete(id);
+    }
+  }
+
+  public void atomicDelete(Project project, List<Change.Id> changeIds) {
+
+    deleteChanges(changeIds);
+
+    for (AccountState a : accountQueryProvider.get().byWatchedProject(project.getNameKey())) {
+      Account.Id accountId = a.account().id();
+      for (ProjectWatchKey watchKey : a.projectWatches().keySet()) {
+        if (project.getNameKey().equals(watchKey.project())) {
+          try {
+            accountsUpdateProvider
+                .get()
+                .update(
+                    "Delete Project Watches via API",
+                    accountId,
+                    u -> u.deleteProjectWatches(singleton(watchKey)));
+          } catch (IOException | ConfigInvalidException e) {
+            log.atSevere().withCause(e).log(
+                "Removing watch entry for user %s in project %s failed.",
+                a.userName().orElse("[unknown]"), project.getName());
+          }
+        }
+      }
+    }
+  }
+}
diff --git a/src/test/java/com/googlesource/gerrit/plugins/deleteproject/DeleteProjectIT.java b/src/test/java/com/googlesource/gerrit/plugins/deleteproject/DeleteProjectIT.java
index 745ae46..d83fac7 100644
--- a/src/test/java/com/googlesource/gerrit/plugins/deleteproject/DeleteProjectIT.java
+++ b/src/test/java/com/googlesource/gerrit/plugins/deleteproject/DeleteProjectIT.java
@@ -34,6 +34,7 @@
 import com.google.gerrit.entities.Project;
 import com.google.gerrit.entities.RefNames;
 import com.google.gerrit.extensions.client.ProjectState;
+import com.google.gerrit.extensions.restapi.RestApiException;
 import com.google.gerrit.server.project.ProjectConfig;
 import com.google.inject.Inject;
 import com.googlesource.gerrit.plugins.deleteproject.DeleteProject.Input;
@@ -87,6 +88,7 @@
     RestResponse r = httpDeleteProjectHelper(true);
     r.assertNoContent();
     assertThat(projectDir.exists()).isFalse();
+    assertAllChangesDeletedInIndex();
   }
 
   @Test
@@ -105,6 +107,8 @@
     RestResponse r = httpDeleteProjectHelper(true);
     r.assertNoContent();
     assertThat(projectDir.exists()).isFalse();
+    assertAllChangesDeletedInIndex();
+    assertWatchRemoved();
   }
 
   @Test
@@ -147,6 +151,19 @@
     adminSshSession.exec(cmd);
     assertThat(adminSshSession.getError()).isNull();
     assertThat(projectDir.exists()).isFalse();
+    assertAllChangesDeletedInIndex();
+  }
+
+  @Test
+  @UseLocalDisk
+  public void testSshDeleteProjectWithWatches() throws Exception {
+    watch(project.get());
+    String cmd = createDeleteCommand(project.get());
+    adminSshSession.exec(cmd);
+    assertThat(adminSshSession.getError()).isNull();
+    assertThat(projectDir.exists()).isFalse();
+    assertAllChangesDeletedInIndex();
+    assertWatchRemoved();
   }
 
   @Test
@@ -224,6 +241,7 @@
     assertThat(isEmpty(archiveFolder.toPath())).isFalse();
     assertThat(containsDeletedProject(archiveFolder.toPath(), project.get())).isTrue();
     assertThat(projectDir.exists()).isFalse();
+    assertAllChangesDeletedInIndex();
   }
 
   @Test
@@ -255,7 +273,7 @@
     assertThat(containsDeletedProject(archiveFolder.toPath().resolve(PARENT_FOLDER), name))
         .isTrue();
     assertThat(projectDir.exists()).isFalse();
-
+    assertAllChangesDeletedInIndex();
     assertThat(parentFolder.toFile().exists()).isFalse();
   }
 
@@ -312,4 +330,12 @@
       return dirStream.anyMatch(d -> d.toString().contains(projectName));
     }
   }
+
+  private void assertAllChangesDeletedInIndex() {
+    assertThat(queryProvider.get().byProject(project)).isEmpty();
+  }
+
+  private void assertWatchRemoved() throws RestApiException {
+    assertThat(gApi.accounts().self().getWatchedProjects()).isEmpty();
+  }
 }