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,162 @@
    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/file1
+ * (this file will be indexed inside testIndexedFile)
+ * - home/file2
+ * - home/included/
+ * - home/included/file
+ * - 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 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_dir = Test::createTmpFilesAndFolders(dirsAndFiles);
+        m_dirPrefix = m_dir->path() + QStringLiteral("/");
+
+        // Creating DB
+        m_db = new Database(m_dir->path());
+        m_db->open(Database::CreateDatabase);
+
+
+        // Initializing config
+        Test::writeIndexerConfig({ m_dirPrefix + rootFolder },
+                                 { m_dirPrefix + excludedFolder } );
+        m_config.forceConfigUpdate();
+    }
+
+    void cleanup() {
+        delete m_db;
+        delete m_dir;
+    }
+
+    void testNoIndexedFiles();
+    void testIndexedFiles();
+    void testDirRenamed();
+private:
+    Database* m_db;
+    QTemporaryDir* m_dir;
+    QString m_dirPrefix;
+    FileIndexerConfig m_config;
 };
 
-using namespace Baloo;
+void UnIndexedFileIteratorTest::testNoIndexedFiles()
+{
+    Transaction tr(m_db, Transaction::ReadOnly);
+    // We want also to be sure that iterator always returns paths that doesn't end with "/",
+    // even if we feed it with the path that does (for example, underlying QDirIterator doesn't work like that)
+    // Other places (see i.e. DocumentUrlDB::put()) rely on it
+    UnIndexedFileIterator it(&m_config, &tr, m_dirPrefix + rootFolder + QStringLiteral("/"));
+    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();
+    }
+    QSet<QString> expectedFiles;
+    expectedFiles << m_dirPrefix + rootFolder;
+    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();
+    }
+    QSet<QString> expectedFiles;
+    expectedFiles << m_dirPrefix + rootFolder;
+    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"