diff --git a/autotests/unit/file/unindexedfileiteratortest.cpp b/autotests/unit/file/unindexedfileiteratortest.cpp
--- a/autotests/unit/file/unindexedfileiteratortest.cpp
+++ b/autotests/unit/file/unindexedfileiteratortest.cpp
@@ -19,30 +19,163 @@
    License along with this library.  If not, see <http://www.gnu.org/licenses/>.
 */
 
-#include "fileindexerconfigutils.h"
-#include "filtereddiriterator.h"
 #include "fileindexerconfig.h"
+#include "unindexedfileiterator.h"
+#include "basicindexingjob.h"
+#include "database.h"
+#include "transaction.h"
+#include "fileindexerconfigutils.h"
 
 #include <QTemporaryDir>
 #include <QTest>
 
-class UnIndexedFileIterator : public QObject
+using namespace Baloo;
+
+/**
+ * Folder structure for the test is following:
+ * - home/
+ * - home/included/
+ * - home/included/file1
+ * (this file will be indexed inside testIndexedFile)
+ * - home/included/file2
+ * - home/included/.hidden
+ * (this file is hidden, so it shouldn't pop up in UnindexedFileIterator)
+ * - home/excluded/
+ * (this whole folder will be excluded)
+ * - home/excluded/file
+ */
+
+static const QString rootFolder = QStringLiteral("home");
+static const QString includedSubfolder = rootFolder + QStringLiteral("/included");
+static const QString excludedFolder = rootFolder + QStringLiteral("/excluded");
+
+static const QString includedSubfolderFile = includedSubfolder + QStringLiteral("/file");
+static const QString hiddenFile = includedSubfolder + QStringLiteral("/.hidden");
+static const QString indexedFile = rootFolder + QStringLiteral("/file1");
+static const QString unindexedFile = rootFolder + QStringLiteral("/file2");
+static const QString excludedFile = excludedFolder + QStringLiteral("/file");
+
+class UnIndexedFileIteratorTest : public QObject
 {
     Q_OBJECT
 private Q_SLOTS:
-    void test();
+    void init() {
+        // Creating DB
+        m_dbdir = new QTemporaryDir();
+        m_db = new Database(m_dbdir->path());
+        m_db->open(Database::CreateDatabase);
+
+        // Creating files & folders (folders path should end with "/")
+        QStringList dirsAndFiles;
+        dirsAndFiles << rootFolder + QStringLiteral("/");
+        dirsAndFiles << includedSubfolder + QStringLiteral("/");
+        dirsAndFiles << excludedFolder + QStringLiteral("/");
+        dirsAndFiles << includedSubfolderFile;
+        dirsAndFiles << indexedFile;
+        dirsAndFiles << unindexedFile;
+        dirsAndFiles << excludedFile;
+        dirsAndFiles << hiddenFile;
+        m_testDir = Test::createTmpFilesAndFolders(dirsAndFiles);
+        m_dirPrefix = m_testDir->path() + QStringLiteral("/");
+
+        // Initializing config
+        Test::writeIndexerConfig({ m_dirPrefix + rootFolder },
+                                 { m_dirPrefix + excludedFolder } );
+        m_config = new FileIndexerConfig();
+    }
+
+    void cleanup() {
+        delete m_db;
+        delete m_config;
+        delete m_dbdir;
+        delete m_testDir;
+    }
+
+    void testNoIndexedFiles();
+    void testIndexedFiles();
+    void testDirRenamed();
+private:
+    Database* m_db;
+    QTemporaryDir* m_dbdir;
+    QTemporaryDir* m_testDir;
+    QString m_dirPrefix;
+    FileIndexerConfig *m_config;
 };
 
-using namespace Baloo;
+void UnIndexedFileIteratorTest::testNoIndexedFiles()
+{
+    Transaction tr(m_db, Transaction::ReadOnly);
+    UnIndexedFileIterator it(m_config, &tr, m_dirPrefix + rootFolder);
+    QSet<QString> unindexedFiles;
+    while (!it.next().isEmpty()) {
+        unindexedFiles << it.filePath();
+    }
 
-void UnIndexedFileIterator::test()
+    QSet<QString> expectedFiles;
+    expectedFiles << m_dirPrefix + rootFolder;
+    expectedFiles << m_dirPrefix + indexedFile;
+    expectedFiles << m_dirPrefix + unindexedFile;
+    expectedFiles << m_dirPrefix + includedSubfolder;
+    expectedFiles << m_dirPrefix + includedSubfolderFile;
+    QCOMPARE(unindexedFiles, expectedFiles);
+}
+
+void UnIndexedFileIteratorTest::testIndexedFiles()
 {
-    // Bah!!
-    // Testing this is complex!
-    // FIXME: How in the world should I test this?
+    // Indexing single file
+    {
+        Transaction tr(m_db, Transaction::ReadWrite);
+        BasicIndexingJob job(m_dirPrefix + indexedFile, QStringLiteral("text/plain"), BasicIndexingJob::NoLevel);
+        job.index();
+        tr.addDocument(job.document());
+        tr.commit();
+    }
+
+    Transaction tr(m_db, Transaction::ReadOnly);
+    UnIndexedFileIterator it(m_config, &tr, m_dirPrefix + rootFolder);
+    QSet<QString> unindexedFiles;
+    while (!it.next().isEmpty()) {
+        unindexedFiles << it.filePath();
+    }
+    // We now also know not only about the file itself,
+    // but also about all directories above
+    QSet<QString> expectedFiles;
+    expectedFiles << m_dirPrefix + unindexedFile;
+    expectedFiles << m_dirPrefix + includedSubfolder;
+    expectedFiles << m_dirPrefix + includedSubfolderFile;
+    QCOMPARE(unindexedFiles, expectedFiles);
 }
 
+void UnIndexedFileIteratorTest::testDirRenamed()
+{
+    QString renamedSubfolder = rootFolder + QStringLiteral("/renamed");
+    // First we index file inside subfolder
+    {
+        Transaction tr(m_db, Transaction::ReadWrite);
+        BasicIndexingJob job(m_dirPrefix + includedSubfolderFile, QStringLiteral("text/plain"), BasicIndexingJob::NoLevel);
+        job.index();
+        tr.addDocument(job.document());
+        tr.commit();
+    }
+    // Then we rename this subfolder
+    QDir dir;
+    dir.rename(m_dirPrefix + includedSubfolder, m_dirPrefix + renamedSubfolder);
+    // And then we perform checks
+    Transaction tr(m_db, Transaction::ReadOnly);
+    UnIndexedFileIterator it(m_config, &tr, m_dirPrefix + rootFolder);
+    QSet<QString> unindexedFiles;
+    while (!it.next().isEmpty()) {
+        unindexedFiles << it.filePath();
+    }
+    // We now also should know not only about the file itself,
+    // but also about all directories above
+    QSet<QString> expectedFiles;
+    expectedFiles << m_dirPrefix + indexedFile;
+    expectedFiles << m_dirPrefix + unindexedFile;
+    expectedFiles << m_dirPrefix + renamedSubfolder;
+    QCOMPARE(unindexedFiles, expectedFiles);
+}
 
-QTEST_GUILESS_MAIN(UnIndexedFileIterator)
+QTEST_GUILESS_MAIN(UnIndexedFileIteratorTest)
 
 #include "unindexedfileiteratortest.moc"
diff --git a/src/file/unindexedfileindexer.cpp b/src/file/unindexedfileindexer.cpp
--- a/src/file/unindexedfileindexer.cpp
+++ b/src/file/unindexedfileindexer.cpp
@@ -59,7 +59,7 @@
                 DocumentOperations ops = DocumentTime;
                 if (it.cTimeChanged()) {
                     ops |= XAttrTerms;
-                    if (tr.documentUrl(id) != it.filePath()) {
+                    if (it.nameChanged()) {
                         ops |= (FileNameTerms | DocumentUrl);
                     }
                 }
diff --git a/src/file/unindexedfileiterator.h b/src/file/unindexedfileiterator.h
--- a/src/file/unindexedfileiterator.h
+++ b/src/file/unindexedfileiterator.h
@@ -48,6 +48,7 @@
     QString mimetype() const;
     bool mTimeChanged() const;
     bool cTimeChanged() const;
+    bool nameChanged() const;
 
 private:
     bool shouldIndex(const QString& filePath, const QString& mimetype);
@@ -61,6 +62,7 @@
 
     bool m_mTimeChanged;
     bool m_cTimeChanged;
+    bool m_nameChanged;
 };
 
 }
diff --git a/src/file/unindexedfileiterator.cpp b/src/file/unindexedfileiterator.cpp
--- a/src/file/unindexedfileiterator.cpp
+++ b/src/file/unindexedfileiterator.cpp
@@ -35,6 +35,7 @@
     , m_iter(config, folder, FilteredDirIterator::FilesAndDirs)
     , m_mTimeChanged(false)
     , m_cTimeChanged(false)
+    , m_nameChanged(false)
 {
 }
 
@@ -62,12 +63,18 @@
     return m_cTimeChanged;
 }
 
+bool UnIndexedFileIterator::nameChanged() const
+{
+    return m_nameChanged;
+}
+
 QString UnIndexedFileIterator::next()
 {
     while (1) {
         const QString filePath = m_iter.next();
         m_mTimeChanged = false;
         m_cTimeChanged = false;
+        m_nameChanged = false;
 
         if (filePath.isEmpty()) {
             m_mimetype.clear();
@@ -103,13 +110,6 @@
 
     DocumentTimeDB::TimeInfo timeInfo = m_transaction->documentTimeInfo(fileId);
 
-    // A folders mtime is updated when a new file is added / removed / renamed
-    // we don't really need to reindex a folder when that happens
-    // In fact, we never need to reindex a folder
-    if (timeInfo.mTime && fileInfo.isDir()) {
-        return false;
-    }
-
     if (timeInfo.mTime != fileInfo.lastModified().toTime_t()) {
         m_mTimeChanged = true;
     }
@@ -119,10 +119,27 @@
         m_cTimeChanged = true;
     }
 
+    if (m_mTimeChanged) {
+        // Since documentUrl is pretty expensive, we want to calculate it only
+        // if we suspect it could have changed
+        const QString oldName = m_transaction->documentUrl(fileId);
+        if (oldName != filePath) {
+            m_nameChanged = true;
+            qCDebug(BALOO) << "name changed:" << oldName << filePath;
+        }
+        // A folders mtime is updated when a new file is added / removed / renamed
+        // we don't really need to reindex a folder when that happens
+        // We only want to reindex folder if it was renamed
+        if (fileInfo.isDir() && !m_nameChanged) {
+            return false;
+        }
+    }
+
     if (m_mTimeChanged || m_cTimeChanged) {
         qCDebug(BALOO) << "mtime/ctime changed:"
             << timeInfo.mTime << fileInfo.lastModified().toTime_t()
             << timeInfo.cTime << fileMTime;
+
         return true;
     }