diff --git a/src/file/fileindexscheduler.h b/src/file/fileindexscheduler.h
--- a/src/file/fileindexscheduler.h
+++ b/src/file/fileindexscheduler.h
@@ -29,6 +29,7 @@
 #include "powerstatemonitor.h"
 #include "indexerstate.h"
 #include "timeestimator.h"
+#include "storagedevices.h"
 
 namespace Baloo {
 
@@ -80,6 +81,7 @@
     Q_SCRIPTABLE void resume() { setSuspend(false); }
     Q_SCRIPTABLE uint getRemainingTime();
     Q_SCRIPTABLE void checkUnindexedFiles();
+    Q_SCRIPTABLE void purgeDeindexableFiles();
     Q_SCRIPTABLE uint getBatchSize();
 
 private Q_SLOTS:
@@ -90,6 +92,7 @@
 
     Database* m_db;
     FileIndexerConfig* m_config;
+    StorageDevices* m_devices;
 
     QStringList m_newFiles;
     QStringList m_modifiedFiles;
@@ -106,6 +109,7 @@
     TimeEstimator m_timeEstimator;
 
     bool m_checkUnindexedFiles;
+    bool m_purgeDeindexableFiles;
 };
 
 }
diff --git a/src/file/fileindexscheduler.cpp b/src/file/fileindexscheduler.cpp
--- a/src/file/fileindexscheduler.cpp
+++ b/src/file/fileindexscheduler.cpp
@@ -26,8 +26,10 @@
 #include "filecontentindexer.h"
 #include "filecontentindexerprovider.h"
 #include "unindexedfileindexer.h"
+#include "indexcleaner.h"
 
 #include "fileindexerconfig.h"
+#include "storagedevices.h"
 
 #include <QTimer>
 #include <QDebug>
@@ -60,6 +62,8 @@
     connect(m_contentIndexer, &FileContentIndexer::newBatchTime, &m_timeEstimator,
             &TimeEstimator::handleNewBatchTime);
 
+    m_devices = new StorageDevices(this);
+
     QDBusConnection::sessionBus().registerObject(QStringLiteral("/scheduler"),
                                                  this, QDBusConnection::ExportScriptableContents);
 }
@@ -135,6 +139,18 @@
         Q_EMIT stateChanged(m_indexerState);
         return;
     }
+
+    if (m_purgeDeindexableFiles) {
+        auto runnable = new IndexCleaner(m_db, m_config, m_devices);
+        connect(runnable, &IndexCleaner::done, this, &FileIndexScheduler::scheduleIndexing);
+
+        m_threadPool.start(runnable);
+        m_purgeDeindexableFiles = false;
+        m_indexerState = DeindexingFileCheck;
+        Q_EMIT stateChanged(m_indexerState);
+        return;
+    }
+
     m_indexerState = Idle;
     Q_EMIT stateChanged(m_indexerState);
 }
@@ -209,6 +225,12 @@
     scheduleIndexing();
 }
 
+void FileIndexScheduler::purgeDeindexableFiles()
+{
+    m_purgeDeindexableFiles = true;
+    scheduleIndexing();
+}
+
 uint FileIndexScheduler::getBatchSize()
 {
     return m_config->maxUncomittedFiles();
diff --git a/src/file/indexcleaner.h b/src/file/indexcleaner.h
--- a/src/file/indexcleaner.h
+++ b/src/file/indexcleaner.h
@@ -20,6 +20,8 @@
 #ifndef BALOO_INDEXCLEANER_H
 #define BALOO_INDEXCLEANER_H
 
+#include "storagedevices.h"
+
 #include <QRunnable>
 #include <QObject>
 
@@ -32,15 +34,16 @@
 {
     Q_OBJECT
 public:
-    IndexCleaner(Database* db, FileIndexerConfig* config);
+    IndexCleaner(Database* db, FileIndexerConfig* config, StorageDevices* devices);
     void run() Q_DECL_OVERRIDE;
 
 Q_SIGNALS:
     void done();
 
 private:
     Database* m_db;
     FileIndexerConfig* m_config;
+    StorageDevices* m_devices;
 };
 }
 
diff --git a/src/file/indexcleaner.cpp b/src/file/indexcleaner.cpp
--- a/src/file/indexcleaner.cpp
+++ b/src/file/indexcleaner.cpp
@@ -19,6 +19,7 @@
 
 #include "indexcleaner.h"
 #include "fileindexerconfig.h"
+#include "storagedevices.h"
 
 #include "database.h"
 #include "transaction.h"
@@ -30,9 +31,10 @@
 
 using namespace Baloo;
 
-IndexCleaner::IndexCleaner(Database* db, FileIndexerConfig* config)
+IndexCleaner::IndexCleaner(Database* db, FileIndexerConfig* config, StorageDevices* devices)
     : m_db(db)
     , m_config(config)
+    , m_devices(devices)
 {
     Q_ASSERT(db);
     Q_ASSERT(config);
@@ -71,9 +73,19 @@
         return false;
     };
 
-    for (const QString& folder : m_config->includeFolders()) {
-        quint64 id = filePathToId(QFile::encodeName(folder));
-        tr.removeRecursively(id, shouldDelete);
+    for (const auto& device: m_devices->allMedia()) {
+        if (!device.isMounted()) {
+            qDebug() << "skipping device:" << device.udi();
+        } else {
+            QString devicePath(device.mountPath() + QLatin1Char('/'));
+
+            for (const QString& folder : m_config->includeFolders()) {
+                if (folder.startsWith(devicePath)) {
+                    quint64 id = filePathToId(QFile::encodeName(folder));
+                    tr.removeRecursively(id, shouldDelete);
+                }
+            }
+        }
     }
     tr.commit();
 
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,
+        DeindexingFileCheck
 };
 
 inline QString stateString(IndexerState state)
@@ -64,6 +65,9 @@
         break;
     case UnindexedFileCheck:
         status = i18n("Checking for unindexed files");
+        break;
+    case DeindexingFileCheck:
+        status = i18n("Checking for deindexable files");
     }
     return status;
 }
diff --git a/src/tools/balooctl/main.cpp b/src/tools/balooctl/main.cpp
--- a/src/tools/balooctl/main.cpp
+++ b/src/tools/balooctl/main.cpp
@@ -82,7 +82,7 @@
     parser.addPositionalArgument(QStringLiteral("restart"), i18n("Restart the file indexer"));
     parser.addPositionalArgument(QStringLiteral("suspend"), i18n("Suspend the file indexer"));
     parser.addPositionalArgument(QStringLiteral("resume"), i18n("Resume the file indexer"));
-    parser.addPositionalArgument(QStringLiteral("check"), i18n("Check for any unindexed files and index them"));
+    parser.addPositionalArgument(QStringLiteral("check"), i18n("Check for changes in the monitored folders"));
     parser.addPositionalArgument(QStringLiteral("index"), i18n("Index the specified files"));
     parser.addPositionalArgument(QStringLiteral("clear"), i18n("Forget the specified files"));
     parser.addPositionalArgument(QStringLiteral("config"), i18n("Modify the Baloo configuration"));
@@ -192,8 +192,9 @@
     }
 
     if (command == QStringLiteral("check")) {
+        schedulerinterface.purgeDeindexableFiles();
         schedulerinterface.checkUnindexedFiles();
-        out << "Started search for unindexed files\n";
+        out << "Started search for changes in monitored folders\n";
         return 0;
     }