diff --git a/src/file/fileindexscheduler.h b/src/file/fileindexscheduler.h
--- a/src/file/fileindexscheduler.h
+++ b/src/file/fileindexscheduler.h
@@ -75,11 +75,14 @@
     void handleFileRemoved(const QString& file);
 
     void scheduleIndexing();
+    void scheduleCheckUnindexedFiles();
+    void scheduleCheckStaleIndexEntries();
 
     Q_SCRIPTABLE void suspend() { setSuspend(true); }
     Q_SCRIPTABLE void resume() { setSuspend(false); }
     Q_SCRIPTABLE uint getRemainingTime();
     Q_SCRIPTABLE void checkUnindexedFiles();
+    Q_SCRIPTABLE void checkStaleIndexEntries();
     Q_SCRIPTABLE uint getBatchSize();
 
 private Q_SLOTS:
@@ -106,6 +109,7 @@
     TimeEstimator m_timeEstimator;
 
     bool m_checkUnindexedFiles;
+    bool m_checkStaleIndexEntries;
 };
 
 }
diff --git a/src/file/fileindexscheduler.cpp b/src/file/fileindexscheduler.cpp
--- a/src/file/fileindexscheduler.cpp
+++ b/src/file/fileindexscheduler.cpp
@@ -26,6 +26,7 @@
 #include "filecontentindexer.h"
 #include "filecontentindexerprovider.h"
 #include "unindexedfileindexer.h"
+#include "indexcleaner.h"
 
 #include "fileindexerconfig.h"
 
@@ -46,6 +47,7 @@
     , m_indexerState(Idle)
     , m_timeEstimator(config, this)
     , m_checkUnindexedFiles(false)
+    , m_checkStaleIndexEntries(false)
 {
     Q_ASSERT(db);
     Q_ASSERT(config);
@@ -137,6 +139,17 @@
         Q_EMIT stateChanged(m_indexerState);
         return;
     }
+
+    if (m_checkStaleIndexEntries) {
+        auto runnable = new IndexCleaner(m_db, m_config);
+        connect(runnable, &IndexCleaner::done, this, &FileIndexScheduler::scheduleIndexing);
+
+        m_threadPool.start(runnable);
+        m_checkStaleIndexEntries = false;
+        m_indexerState = StaleIndexEntriesClean;
+        Q_EMIT stateChanged(m_indexerState);
+        return;
+    }
     m_indexerState = Idle;
     Q_EMIT stateChanged(m_indexerState);
 }
@@ -203,12 +216,29 @@
     return m_timeEstimator.calculateTimeLeft(m_provider.size());
 }
 
+void FileIndexScheduler::scheduleCheckUnindexedFiles()
+{
+    m_checkUnindexedFiles = true;
+}
+
 void FileIndexScheduler::checkUnindexedFiles()
 {
     m_checkUnindexedFiles = true;
     scheduleIndexing();
 }
 
+void FileIndexScheduler::scheduleCheckStaleIndexEntries()
+{
+    m_checkStaleIndexEntries = true;
+}
+
+void FileIndexScheduler::checkStaleIndexEntries()
+{
+    m_checkStaleIndexEntries = true;
+    scheduleIndexing();
+}
+
+
 uint FileIndexScheduler::getBatchSize()
 {
     return m_config->maxUncomittedFiles();
diff --git a/src/file/indexerstate.h b/src/file/indexerstate.h
--- a/src/file/indexerstate.h
+++ b/src/file/indexerstate.h
@@ -34,7 +34,8 @@
         ModifiedFiles,
         XAttrFiles,
         ContentIndexing,
-        UnindexedFileCheck
+        UnindexedFileCheck,
+        StaleIndexEntriesClean
 };
 
 inline QString stateString(IndexerState state)
@@ -64,6 +65,9 @@
         break;
     case UnindexedFileCheck:
         status = i18n("Checking for unindexed files");
+        break;
+    case StaleIndexEntriesClean:
+        status = i18n("Checking for stale index entries");
     }
     return status;
 }
diff --git a/src/file/mainhub.cpp b/src/file/mainhub.cpp
--- a/src/file/mainhub.cpp
+++ b/src/file/mainhub.cpp
@@ -51,6 +51,10 @@
     bus.registerObject(QStringLiteral("/"), this, QDBusConnection::ExportAllSlots |
                         QDBusConnection::ExportScriptableSignals | QDBusConnection::ExportAdaptors);
 
+    if (!m_config->isInitialRun()) {
+        m_fileIndexScheduler.scheduleCheckUnindexedFiles();
+        m_fileIndexScheduler.scheduleCheckStaleIndexEntries();
+    }
     QTimer::singleShot(0, &m_fileWatcher, &FileWatch::watchIndexedFolders);
 }