diff --git a/src/main/java/com/ericsson/gerrit/plugins/eventslog/EventCleanerPool.java b/src/main/java/com/ericsson/gerrit/plugins/eventslog/EventCleanerPool.java
new file mode 100644
index 0000000..9efdeae
--- /dev/null
+++ b/src/main/java/com/ericsson/gerrit/plugins/eventslog/EventCleanerPool.java
@@ -0,0 +1,25 @@
+// Copyright (C) 2018 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.ericsson.gerrit.plugins.eventslog;
+
+import static java.lang.annotation.RetentionPolicy.RUNTIME;
+
+import com.google.inject.BindingAnnotation;
+import java.lang.annotation.Retention;
+
+/** Annotation applied to a ScheduledThreadPoolExecutor. */
+@Retention(RUNTIME)
+@BindingAnnotation
+public @interface EventCleanerPool {}
diff --git a/src/main/java/com/ericsson/gerrit/plugins/eventslog/EventCleanerQueue.java b/src/main/java/com/ericsson/gerrit/plugins/eventslog/EventCleanerQueue.java
new file mode 100644
index 0000000..d8e2aff
--- /dev/null
+++ b/src/main/java/com/ericsson/gerrit/plugins/eventslog/EventCleanerQueue.java
@@ -0,0 +1,49 @@
+// Copyright (C) 2018 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.ericsson.gerrit.plugins.eventslog;
+
+import com.google.gerrit.extensions.events.LifecycleListener;
+import com.google.gerrit.server.git.WorkQueue;
+import com.google.inject.Inject;
+import com.google.inject.Singleton;
+import java.util.concurrent.ScheduledThreadPoolExecutor;
+
+@Singleton
+public class EventCleanerQueue implements LifecycleListener {
+  private final WorkQueue workQueue;
+  private WorkQueue.Executor pool;
+
+  @Inject
+  public EventCleanerQueue(WorkQueue workQueue) {
+    this.workQueue = workQueue;
+  }
+
+  @Override
+  public void start() {
+    pool = workQueue.createQueue(1, "[events-log] Remove events");
+  }
+
+  @Override
+  public void stop() {
+    if (pool != null) {
+      pool.unregisterWorkQueue();
+      pool = null;
+    }
+  }
+
+  public ScheduledThreadPoolExecutor getPool() {
+    return pool;
+  }
+}
diff --git a/src/main/java/com/ericsson/gerrit/plugins/eventslog/EventModule.java b/src/main/java/com/ericsson/gerrit/plugins/eventslog/EventModule.java
index 906c0e8..56f8802 100644
--- a/src/main/java/com/ericsson/gerrit/plugins/eventslog/EventModule.java
+++ b/src/main/java/com/ericsson/gerrit/plugins/eventslog/EventModule.java
@@ -14,8 +14,10 @@
 
 package com.ericsson.gerrit.plugins.eventslog;
 
+import com.ericsson.gerrit.plugins.eventslog.sql.EventsLogCleaner;
 import com.google.gerrit.common.EventListener;
 import com.google.gerrit.extensions.events.LifecycleListener;
+import com.google.gerrit.extensions.events.ProjectDeletedListener;
 import com.google.gerrit.extensions.registration.DynamicSet;
 import com.google.inject.AbstractModule;
 import com.google.inject.Provides;
@@ -31,7 +33,11 @@
     bind(EventQueue.class).in(Scopes.SINGLETON);
     bind(EventHandler.class).in(Scopes.SINGLETON);
     bind(LifecycleListener.class).annotatedWith(UniqueAnnotations.create()).to(EventQueue.class);
+    bind(LifecycleListener.class)
+        .annotatedWith(UniqueAnnotations.create())
+        .to(EventCleanerQueue.class);
     DynamicSet.bind(binder(), EventListener.class).to(EventHandler.class);
+    DynamicSet.bind(binder(), ProjectDeletedListener.class).to(EventsLogCleaner.class);
   }
 
   @Provides
@@ -39,4 +45,10 @@
   ScheduledThreadPoolExecutor provideEventPool(EventQueue queue) {
     return queue.getPool();
   }
+
+  @Provides
+  @EventCleanerPool
+  ScheduledThreadPoolExecutor provideEventCleanerPool(EventCleanerQueue queue) {
+    return queue.getPool();
+  }
 }
diff --git a/src/main/java/com/ericsson/gerrit/plugins/eventslog/sql/EventsLogCleaner.java b/src/main/java/com/ericsson/gerrit/plugins/eventslog/sql/EventsLogCleaner.java
new file mode 100644
index 0000000..6422944
--- /dev/null
+++ b/src/main/java/com/ericsson/gerrit/plugins/eventslog/sql/EventsLogCleaner.java
@@ -0,0 +1,48 @@
+// Copyright (C) 2018 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.ericsson.gerrit.plugins.eventslog.sql;
+
+import com.ericsson.gerrit.plugins.eventslog.EventCleanerPool;
+import com.google.gerrit.extensions.events.ProjectDeletedListener;
+import com.google.inject.Inject;
+import com.google.inject.Singleton;
+import java.util.concurrent.ScheduledThreadPoolExecutor;
+
+@Singleton
+public class EventsLogCleaner implements ProjectDeletedListener {
+  private final SQLClient eventsDb;
+  private final SQLClient localEventsDb;
+  private ScheduledThreadPoolExecutor pool;
+
+  @Inject
+  EventsLogCleaner(
+      @EventsDb SQLClient eventsDb,
+      @LocalEventsDb SQLClient localEventsDb,
+      @EventCleanerPool ScheduledThreadPoolExecutor pool) {
+    this.eventsDb = eventsDb;
+    this.localEventsDb = localEventsDb;
+    this.pool = pool;
+  }
+
+  @Override
+  public void onProjectDeleted(Event event) {
+    removeProjectEventsAsync(event.getProjectName());
+  }
+
+  public void removeProjectEventsAsync(String projectName) {
+    pool.submit(() -> eventsDb.removeProjectEvents(projectName));
+    pool.submit(() -> localEventsDb.removeProjectEvents(projectName));
+  }
+}
diff --git a/src/main/java/com/ericsson/gerrit/plugins/eventslog/sql/SQLStore.java b/src/main/java/com/ericsson/gerrit/plugins/eventslog/sql/SQLStore.java
index aa579af..cdf104f 100644
--- a/src/main/java/com/ericsson/gerrit/plugins/eventslog/sql/SQLStore.java
+++ b/src/main/java/com/ericsson/gerrit/plugins/eventslog/sql/SQLStore.java
@@ -54,6 +54,7 @@
 
   private final ProjectControl.GenericFactory projectControlFactory;
   private final Provider<CurrentUser> userProvider;
+  private final EventsLogCleaner eventsLogCleaner;
   private SQLClient eventsDb;
   private SQLClient localEventsDb;
   private final int maxAge;
@@ -73,7 +74,8 @@
       EventsLogConfig cfg,
       @EventsDb SQLClient eventsDb,
       @LocalEventsDb SQLClient localEventsDb,
-      @EventPool ScheduledThreadPoolExecutor pool) {
+      @EventPool ScheduledThreadPoolExecutor pool,
+      EventsLogCleaner eventsLogCleaner) {
     this.maxAge = cfg.getMaxAge();
     this.maxTries = cfg.getMaxTries();
     this.waitTime = cfg.getWaitTime();
@@ -83,6 +85,7 @@
     this.userProvider = userProvider;
     this.eventsDb = eventsDb;
     this.localEventsDb = localEventsDb;
+    this.eventsLogCleaner = eventsLogCleaner;
     this.pool = pool;
     this.localPath = cfg.getLocalStorePath();
   }
@@ -123,7 +126,7 @@
         log.warn(
             "Database contains a non-existing project, {}; removing project from database",
             projectName);
-        eventsDb.removeProjectEvents(projectName);
+        eventsLogCleaner.removeProjectEventsAsync(projectName);
       } catch (IOException e) {
         log.warn("Cannot get project visibility info for {} from cache", projectName, e);
       }
diff --git a/src/test/java/com/ericsson/gerrit/plugins/eventslog/sql/EventsLogCleanerTest.java b/src/test/java/com/ericsson/gerrit/plugins/eventslog/sql/EventsLogCleanerTest.java
new file mode 100644
index 0000000..cd06855
--- /dev/null
+++ b/src/test/java/com/ericsson/gerrit/plugins/eventslog/sql/EventsLogCleanerTest.java
@@ -0,0 +1,63 @@
+// Copyright (C) 2018 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.ericsson.gerrit.plugins.eventslog.sql;
+
+import static org.mockito.Mockito.times;
+import static org.mockito.Mockito.verify;
+import static org.mockito.Mockito.when;
+
+import com.ericsson.gerrit.plugins.eventslog.EventsLogConfig;
+import com.google.gerrit.extensions.events.ProjectDeletedListener;
+import java.util.concurrent.ScheduledThreadPoolExecutor;
+import java.util.concurrent.TimeUnit;
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.mockito.Mock;
+import org.mockito.junit.MockitoJUnitRunner;
+
+@RunWith(MockitoJUnitRunner.class)
+public class EventsLogCleanerTest {
+  private static final String PROJECT = "testProject";
+
+  @Mock private EventsLogConfig cfgMock;
+  @Mock private EventsLogCleaner logCleanerMock;
+  @Mock private SQLClient eventsDb;
+  @Mock private SQLClient localEventsDb;
+  @Mock private ProjectDeletedListener.Event event;
+
+  private ScheduledThreadPoolExecutor executor = new ScheduledThreadPoolExecutor(1);
+  private EventsLogCleaner eventsLogCleaner;
+
+  @Before
+  public void setUp() throws Exception {
+    when(event.getProjectName()).thenReturn(PROJECT);
+    eventsLogCleaner = new EventsLogCleaner(eventsDb, localEventsDb, executor);
+  }
+
+  @Test
+  public void testOnProjectDeleted() throws InterruptedException {
+    eventsLogCleaner.onProjectDeleted(event);
+    executor.awaitTermination(1, TimeUnit.SECONDS);
+    verify(eventsDb, times(1)).removeProjectEvents(PROJECT);
+    verify(localEventsDb, times(1)).removeProjectEvents(PROJECT);
+  }
+
+  @After
+  public void tearDown() throws Exception {
+    executor.shutdownNow();
+  }
+}
diff --git a/src/test/java/com/ericsson/gerrit/plugins/eventslog/sql/SQLStoreTest.java b/src/test/java/com/ericsson/gerrit/plugins/eventslog/sql/SQLStoreTest.java
index c0b4650..3b0a19e 100644
--- a/src/test/java/com/ericsson/gerrit/plugins/eventslog/sql/SQLStoreTest.java
+++ b/src/test/java/com/ericsson/gerrit/plugins/eventslog/sql/SQLStoreTest.java
@@ -72,6 +72,8 @@
   @Mock private ProjectControl.GenericFactory pcFactoryMock;
   @Mock private Provider<CurrentUser> userProviderMock;
   @Mock private EventsLogConfig cfgMock;
+  @Mock private EventsLogCleaner logCleanerMock;
+
   private SQLClient eventsDb;
   private SQLClient localEventsDb;
   private SQLStore store;
@@ -99,7 +101,14 @@
     eventsDb = new SQLClient(TEST_URL, TEST_OPTIONS);
     localEventsDb = new SQLClient(TEST_LOCAL_URL, TEST_OPTIONS);
     store =
-        new SQLStore(pcFactoryMock, userProviderMock, cfgMock, eventsDb, localEventsDb, poolMock);
+        new SQLStore(
+            pcFactoryMock,
+            userProviderMock,
+            cfgMock,
+            eventsDb,
+            localEventsDb,
+            poolMock,
+            logCleanerMock);
     store.start();
   }
 
@@ -160,6 +169,7 @@
     store.storeEvent(mockEvent);
     List<String> events = store.queryChangeEvents(GENERIC_QUERY);
     assertThat(events).isEmpty();
+    verify(logCleanerMock).removeProjectEventsAsync(mockEvent.project);
     tearDown();
   }
 
@@ -187,7 +197,14 @@
     doThrow(exceptions).doNothing().when(eventsDb).storeEvent(mockEvent);
     doThrow(exceptions).doNothing().when(eventsDb).queryOne();
     store =
-        new SQLStore(pcFactoryMock, userProviderMock, cfgMock, eventsDb, localEventsDb, poolMock);
+        new SQLStore(
+            pcFactoryMock,
+            userProviderMock,
+            cfgMock,
+            eventsDb,
+            localEventsDb,
+            poolMock,
+            logCleanerMock);
     store.start();
     store.storeEvent(mockEvent);
     verify(eventsDb, times(3)).storeEvent(mockEvent);
@@ -204,7 +221,14 @@
     doThrow(exceptions).doNothing().when(eventsDb).storeEvent(mockEvent);
     doThrow(exceptions).doNothing().when(eventsDb).queryOne();
     store =
-        new SQLStore(pcFactoryMock, userProviderMock, cfgMock, eventsDb, localEventsDb, poolMock);
+        new SQLStore(
+            pcFactoryMock,
+            userProviderMock,
+            cfgMock,
+            eventsDb,
+            localEventsDb,
+            poolMock,
+            logCleanerMock);
     store.start();
     store.storeEvent(mockEvent);
     verify(eventsDb, times(3)).storeEvent(mockEvent);
@@ -218,7 +242,14 @@
     setUpClientMock();
     doThrow(new SQLException(MSG)).when(eventsDb).storeEvent(mockEvent);
     store =
-        new SQLStore(pcFactoryMock, userProviderMock, cfgMock, eventsDb, localEventsDb, poolMock);
+        new SQLStore(
+            pcFactoryMock,
+            userProviderMock,
+            cfgMock,
+            eventsDb,
+            localEventsDb,
+            poolMock,
+            logCleanerMock);
     store.start();
     store.storeEvent(mockEvent);
     verify(eventsDb, times(1)).storeEvent(mockEvent);
@@ -234,7 +265,14 @@
     doThrow(exceptions).doNothing().when(eventsDb).storeEvent(mockEvent);
     doThrow(exceptions).doNothing().when(eventsDb).queryOne();
     store =
-        new SQLStore(pcFactoryMock, userProviderMock, cfgMock, eventsDb, localEventsDb, poolMock);
+        new SQLStore(
+            pcFactoryMock,
+            userProviderMock,
+            cfgMock,
+            eventsDb,
+            localEventsDb,
+            poolMock,
+            logCleanerMock);
     store.start();
     store.storeEvent(mockEvent);
     verify(eventsDb, times(1)).storeEvent(mockEvent);
@@ -247,7 +285,14 @@
     doThrow(new SQLException(new ConnectException())).when(eventsDb).createDBIfNotCreated();
     doThrow(new SQLException()).when(eventsDb).queryOne();
     store =
-        new SQLStore(pcFactoryMock, userProviderMock, cfgMock, eventsDb, localEventsDb, poolMock);
+        new SQLStore(
+            pcFactoryMock,
+            userProviderMock,
+            cfgMock,
+            eventsDb,
+            localEventsDb,
+            poolMock,
+            logCleanerMock);
     store.start();
     store.storeEvent(mockEvent);
     store.queryChangeEvents(GENERIC_QUERY);
@@ -271,7 +316,14 @@
     eventsDb = new SQLClient(TEST_URL, TEST_OPTIONS);
     localEventsDb = new SQLClient(TEST_LOCAL_URL, TEST_OPTIONS);
     store =
-        new SQLStore(pcFactoryMock, userProviderMock, cfgMock, eventsDb, localEventsDb, poolMock);
+        new SQLStore(
+            pcFactoryMock,
+            userProviderMock,
+            cfgMock,
+            eventsDb,
+            localEventsDb,
+            poolMock,
+            logCleanerMock);
 
     localEventsDb.createDBIfNotCreated();
     localEventsDb.storeEvent(mockEvent);
@@ -292,7 +344,14 @@
     doThrow(new SQLException(new ConnectException())).when(eventsDb).createDBIfNotCreated();
     doThrow(new SQLException()).when(eventsDb).queryOne();
     store =
-        new SQLStore(pcFactoryMock, userProviderMock, cfgMock, eventsDb, localEventsDb, poolMock);
+        new SQLStore(
+            pcFactoryMock,
+            userProviderMock,
+            cfgMock,
+            eventsDb,
+            localEventsDb,
+            poolMock,
+            logCleanerMock);
     store.start();
     verify(localEventsDb).createDBIfNotCreated();
   }
@@ -304,7 +363,14 @@
     doThrow(new SQLException(new ConnectException())).when(eventsDb).createDBIfNotCreated();
     doThrow(new SQLException()).when(eventsDb).queryOne();
     store =
-        new SQLStore(pcFactoryMock, userProviderMock, cfgMock, eventsDb, localEventsDb, poolMock);
+        new SQLStore(
+            pcFactoryMock,
+            userProviderMock,
+            cfgMock,
+            eventsDb,
+            localEventsDb,
+            poolMock,
+            logCleanerMock);
     store.start();
     store.storeEvent(mockEvent);
     verify(localEventsDb).storeEvent(mockEvent);
@@ -318,7 +384,14 @@
     doThrow(new SQLException(new ConnectException())).when(eventsDb).createDBIfNotCreated();
     doThrow(new SQLException()).when(eventsDb).queryOne();
     store =
-        new SQLStore(pcFactoryMock, userProviderMock, cfgMock, eventsDb, localEventsDb, poolMock);
+        new SQLStore(
+            pcFactoryMock,
+            userProviderMock,
+            cfgMock,
+            eventsDb,
+            localEventsDb,
+            poolMock,
+            logCleanerMock);
     store.start();
     store.storeEvent(mockEvent);
     verify(localEventsDb).storeEvent(mockEvent);
@@ -336,7 +409,14 @@
     when(localEventsDb.dbExists()).thenReturn(true);
     when(localEventsDb.getAll()).thenReturn(ImmutableList.of(mock(SQLEntry.class)));
     store =
-        new SQLStore(pcFactoryMock, userProviderMock, cfgMock, eventsDb, localEventsDb, poolMock);
+        new SQLStore(
+            pcFactoryMock,
+            userProviderMock,
+            cfgMock,
+            eventsDb,
+            localEventsDb,
+            poolMock,
+            logCleanerMock);
     store.start();
     poolMock.scheduleWithFixedDelay(store.new CheckConnectionTask(), 0, 0, TimeUnit.MILLISECONDS);
     verify(localEventsDb, times(2)).removeOldEvents(0);
@@ -368,7 +448,14 @@
     }
 
     store =
-        new SQLStore(pcFactoryMock, userProviderMock, cfgMock, eventsDb, localEventsDb, poolMock);
+        new SQLStore(
+            pcFactoryMock,
+            userProviderMock,
+            cfgMock,
+            eventsDb,
+            localEventsDb,
+            poolMock,
+            logCleanerMock);
     store.start();
     verify(eventsDb).queryOne();
     verify(eventsDb).storeEvent(any(String.class), any(Timestamp.class), any(String.class));