diff --git a/wallpapers/image/image.cpp b/wallpapers/image/image.cpp
--- a/wallpapers/image/image.cpp
+++ b/wallpapers/image/image.cpp
@@ -769,7 +769,7 @@
         m_currentSlide += 1;
     }
      //We are starting again - avoid having the same random order when we restart the slideshow
-    if (m_slideshowMode == Random && previousSlide == m_slideFilterModel->rowCount() - 1) {
+    if (m_slideshowMode == Random && m_currentSlide == 0) {
             m_slideFilterModel->invalidate();
     }
     QUrl next = m_slideFilterModel->index(m_currentSlide, 0).data(BackgroundListModel::PathRole).toUrl();
diff --git a/wallpapers/image/slidefiltermodel.h b/wallpapers/image/slidefiltermodel.h
--- a/wallpapers/image/slidefiltermodel.h
+++ b/wallpapers/image/slidefiltermodel.h
@@ -22,7 +22,7 @@
 #include <image.h>
 
 #include <QSortFilterProxyModel>
-
+#include <QVector>
 
 class SlideFilterModel : public QSortFilterProxyModel {
 
@@ -34,7 +34,9 @@
     SlideFilterModel(QObject* parent);
     bool lessThan(const QModelIndex& source_left, const QModelIndex& source_right) const override;
     bool filterAcceptsRow(int source_row, const QModelIndex& source_parent) const override;
+    void setSourceModel(QAbstractItemModel *sourceModel) override;
     void setSortingMode(Image::SlideshowMode mode);
+    void invalidate();
     void invalidateFilter();
 
     Q_INVOKABLE int indexOf(const QString& path);
@@ -44,6 +46,9 @@
     void usedInConfigChanged();
 
 private:
+    void buildRandomOrder();
+
+    QVector<int> m_randomOrder;
     Image::SlideshowMode m_SortingMode;
     bool m_usedInConfig;
 };
diff --git a/wallpapers/image/slidefiltermodel.cpp b/wallpapers/image/slidefiltermodel.cpp
--- a/wallpapers/image/slidefiltermodel.cpp
+++ b/wallpapers/image/slidefiltermodel.cpp
@@ -24,6 +24,8 @@
 #include <QRandomGenerator>
 #include <QFileInfo>
 
+#include <algorithm>
+
 SlideFilterModel::SlideFilterModel(QObject* parent)
     : QSortFilterProxyModel{parent}
     , m_SortingMode{Image::Random}
@@ -39,11 +41,43 @@
     return m_usedInConfig || index.data(BackgroundListModel::ToggleRole).toBool();
 }
 
+void SlideFilterModel::setSourceModel(QAbstractItemModel *sourceModel)
+{
+    if (this->sourceModel()) {
+        disconnect(this->sourceModel(), nullptr, this, nullptr);
+    }
+    QSortFilterProxyModel::setSourceModel(sourceModel);
+    if (m_SortingMode == Image::Random && !m_usedInConfig) {
+        buildRandomOrder();
+    }
+    if(sourceModel) {
+        connect(sourceModel, &QAbstractItemModel::rowsInserted, this, [this] {
+            if (m_SortingMode !=  Image::Random || m_usedInConfig) {
+                return;
+            }
+            const int old_count = m_randomOrder.size();
+            m_randomOrder.resize(this->sourceModel()->rowCount());
+            std::iota(m_randomOrder.begin() + old_count, m_randomOrder.end(), old_count);
+        });
+        connect(sourceModel, &QAbstractItemModel::rowsRemoved, this, [this] {
+            if (m_SortingMode !=  Image::Random || m_usedInConfig) {
+                return;
+            }
+            m_randomOrder.erase(std::remove_if(m_randomOrder.begin(), m_randomOrder.end(), [this] (const int v) {
+                return v >= this->sourceModel()->rowCount();
+            }), m_randomOrder.end());
+        });
+    }
+}
+
 bool SlideFilterModel::lessThan(const QModelIndex& source_left, const QModelIndex& source_right) const
 {
         switch (m_SortingMode) {
         case Image::Random:
-            return (*QRandomGenerator::system())() % 2 == 0;
+            if (m_usedInConfig) {
+                return source_left.row() < source_right.row();
+            }
+            return m_randomOrder.indexOf(source_left.row()) < m_randomOrder.indexOf(source_right.row());
         case Image::Alphabetical:
             return QSortFilterProxyModel::lessThan(source_left, source_right);
         case Image::AlphabeticalReversed:
@@ -66,10 +100,18 @@
 
 void SlideFilterModel::setSortingMode(Image::SlideshowMode mode)
 {
-    m_SortingMode = mode;
-    if (!(m_usedInConfig && mode == Image::Random)) {
-        QSortFilterProxyModel::invalidate();
+    if (m_SortingMode == Image::Random && !m_usedInConfig) {
+        buildRandomOrder();
     }
+    QSortFilterProxyModel::invalidate();
+}
+
+void SlideFilterModel::invalidate()
+{
+    if (m_SortingMode == Image::Random && !m_usedInConfig) {
+        std::random_shuffle(m_randomOrder.begin(), m_randomOrder.end());
+    }
+    QSortFilterProxyModel::invalidate();
 }
 
 void SlideFilterModel::invalidateFilter()
@@ -88,3 +130,12 @@
     auto sourceIndex = mapToSource(index(rowIndex, 0));
     static_cast<SlideModel*>(sourceModel())->openContainingFolder(sourceIndex.row());
 }
+
+void SlideFilterModel::buildRandomOrder()
+{
+    if (sourceModel()) {
+        m_randomOrder.resize(sourceModel()->rowCount());
+        std::iota(m_randomOrder.begin(), m_randomOrder.end(), 0);
+        std::random_shuffle(m_randomOrder.begin(), m_randomOrder.end());
+    }
+}