diff --git a/abstract_client.h b/abstract_client.h
--- a/abstract_client.h
+++ b/abstract_client.h
@@ -94,7 +94,7 @@
     /**
      * The x11 ids for all desktops this client is in. On X11 this list will always have a length of 1
      **/
-    Q_PROPERTY(QVector<int> x11DesktopIds READ x11DesktopIds NOTIFY x11DesktopIdsChanged)
+    Q_PROPERTY(QVector<uint> x11DesktopIds READ x11DesktopIds NOTIFY x11DesktopIdsChanged)
     /**
      * Indicates that the window should not be included on a taskbar.
      **/
@@ -428,7 +428,10 @@
     virtual bool performMouseCommand(Options::MouseCommand, const QPoint &globalPos);
     void setOnAllDesktops(bool set);
     void setDesktop(int);
-    Q_INVOKABLE virtual void unSetDesktop(int desktop);
+    void enterDesktop(VirtualDesktop *desktop);
+    void leaveDesktop(VirtualDesktop *desktop);
+    void setDesktops(QVector<VirtualDesktop *> desktops);
+
     int desktop() const override {
         return m_desktops.isEmpty() ? (int)NET::OnAllDesktops : m_desktops.last()->x11DesktopNumber();
     }
@@ -438,7 +441,7 @@
     void removeDesktop(VirtualDesktop *desktop) {
         m_desktops.removeAll(desktop);
     }
-    QVector<int> x11DesktopIds() const;
+    QVector<uint> x11DesktopIds() const;
 
     void setMinimized(bool set);
     /**
@@ -1104,8 +1107,6 @@
 
     bool tabTo(AbstractClient *other, bool behind, bool activate);
 
-    void setDesktops(QVector<VirtualDesktop *> desktops);
-
 private:
     void handlePaletteChange();
     QSharedPointer<TabBox::TabBoxClientImpl> m_tabBoxClient;
diff --git a/abstract_client.cpp b/abstract_client.cpp
--- a/abstract_client.cpp
+++ b/abstract_client.cpp
@@ -571,24 +571,29 @@
     Q_UNUSED(was_desk)
 }
 
-void AbstractClient::unSetDesktop(int desktop)
+void AbstractClient::enterDesktop(VirtualDesktop *virtualDesktop)
 {
-    // Case in which we are on all desktops and gets asked to unset
-    if (desktop == NET::OnAllDesktops) {
-        if (m_desktops.isEmpty()) {
-            setOnAllDesktops(false);
-        }
+    if (m_desktops.contains(virtualDesktop)) {
         return;
     }
+    auto desktops = m_desktops;
+    desktops.append(virtualDesktop);
+    setDesktops(desktops);
+}
 
-    // Out of range
-    if (desktop < 1 || desktop > VirtualDesktopManager::self()->count()) {
-        return;
+void AbstractClient::leaveDesktop(VirtualDesktop *virtualDesktop)
+{
+    QVector<VirtualDesktop*> currentDesktops;
+    if (m_desktops.isEmpty()) {
+        currentDesktops = VirtualDesktopManager::self()->desktops();
+    } else {
+        currentDesktops = m_desktops;
     }
 
-    VirtualDesktop *virtualDesktop = VirtualDesktopManager::self()->desktopForX11Id(desktop);
-    Q_ASSERT(virtualDesktop);
-    auto desktops = m_desktops;
+    if (!currentDesktops.contains(virtualDesktop)) {
+        return;
+    }
+    auto desktops = currentDesktops;
     desktops.removeOne(virtualDesktop);
     setDesktops(desktops);
 }
@@ -604,10 +609,10 @@
         setDesktop(VirtualDesktopManager::self()->current());
 }
 
-QVector<int> AbstractClient::x11DesktopIds() const
+QVector<uint> AbstractClient::x11DesktopIds() const
 {
     const auto desks = desktops();
-    QVector<int> x11Ids;
+    QVector<uint> x11Ids;
     x11Ids.reserve(desks.count());
     std::transform(desks.constBegin(), desks.constEnd(),
         std::back_inserter(x11Ids),
@@ -999,21 +1004,21 @@
         [this] (const QString &desktopId) {
             VirtualDesktop *vd = VirtualDesktopManager::self()->desktopForId(desktopId.toUtf8());
             if (vd) {
-                workspace()->sendClientToDesktop(this, vd->x11DesktopNumber(), false);
+                enterDesktop(vd);
             }
         }
     );
     connect(w, &PlasmaWindowInterface::enterNewPlasmaVirtualDesktopRequested, this,
         [this] () {
             VirtualDesktopManager::self()->setCount(VirtualDesktopManager::self()->count() + 1);
-            workspace()->sendClientToDesktop(this, VirtualDesktopManager::self()->count(), false);
+            enterDesktop(VirtualDesktopManager::self()->desktops().last());
         }
     );
     connect(w, &PlasmaWindowInterface::leavePlasmaVirtualDesktopRequested, this,
         [this] (const QString &desktopId) {
             VirtualDesktop *vd = VirtualDesktopManager::self()->desktopForId(desktopId.toUtf8());
             if (vd) {
-                unSetDesktop(vd->x11DesktopNumber());
+                leaveDesktop(vd);
             }
         }
     );
diff --git a/autotests/integration/virtual_desktop_test.cpp b/autotests/integration/virtual_desktop_test.cpp
--- a/autotests/integration/virtual_desktop_test.cpp
+++ b/autotests/integration/virtual_desktop_test.cpp
@@ -210,41 +210,58 @@
     QCOMPARE(VirtualDesktopManager::self()->currentDesktop(), client->desktops().first());
 
     //Set the window on desktop 2 as well
-    client->setDesktop(2u);
+    client->enterDesktop(VirtualDesktopManager::self()->desktopForX11Id(2));
     QCOMPARE(client->desktops().count(), 2u);
     QCOMPARE(VirtualDesktopManager::self()->desktops()[2], client->desktops()[0]);
     QCOMPARE(VirtualDesktopManager::self()->desktops()[1], client->desktops()[1]);
     QVERIFY(client->isOnDesktop(2));
     QVERIFY(client->isOnDesktop(3));
 
     //leave desktop 3
-    client->unSetDesktop(3);
+    client->leaveDesktop(VirtualDesktopManager::self()->desktopForX11Id(3));
     QCOMPARE(client->desktops().count(), 1u);
     //leave desktop 2
-    client->unSetDesktop(2);
+    client->leaveDesktop(VirtualDesktopManager::self()->desktopForX11Id(2));
     QCOMPARE(client->desktops().count(), 0u);
     //we should be on all desktops now
     QVERIFY(client->isOnAllDesktops());
     //put on desktop 1
-    client->setDesktop(1);
+    client->enterDesktop(VirtualDesktopManager::self()->desktopForX11Id(1));
     QVERIFY(client->isOnDesktop(1));
     QVERIFY(!client->isOnDesktop(2));
     QVERIFY(!client->isOnDesktop(3));
     QCOMPARE(client->desktops().count(), 1u);
     //put on desktop 2
-    client->setDesktop(2);
+    client->enterDesktop(VirtualDesktopManager::self()->desktopForX11Id(2));
     QVERIFY(client->isOnDesktop(1));
     QVERIFY(client->isOnDesktop(2));
     QVERIFY(!client->isOnDesktop(3));
     QCOMPARE(client->desktops().count(), 2u);
     //put on desktop 3
-    client->setDesktop(3);
+    client->enterDesktop(VirtualDesktopManager::self()->desktopForX11Id(3));
     QVERIFY(client->isOnDesktop(1));
     QVERIFY(client->isOnDesktop(2));
     QVERIFY(client->isOnDesktop(3));
-    QVERIFY(client->isOnAllDesktops());
-    //when it gets on all desktops, it loses all desktops()
+    QCOMPARE(client->desktops().count(), 3u);
+
+    //entering twice dooes nothing
+    client->enterDesktop(VirtualDesktopManager::self()->desktopForX11Id(3));
+    QCOMPARE(client->desktops().count(), 3u);
+
+    //adding to "all desktops" results in just that one desktop
+    client->setOnAllDesktops(true);
+    QCOMPARE(client->desktops().count(), 0u);
+    client->enterDesktop(VirtualDesktopManager::self()->desktopForX11Id(3));
+    QVERIFY(client->isOnDesktop(3));
+    QCOMPARE(client->desktops().count(), 1u);
+
+    //leaving a desktop on "all desktops" puts on everything else
+    client->setOnAllDesktops(true);
     QCOMPARE(client->desktops().count(), 0u);
+    client->leaveDesktop(VirtualDesktopManager::self()->desktopForX11Id(3));
+    QVERIFY(client->isOnDesktop(1));
+    QVERIFY(client->isOnDesktop(2));
+    QCOMPARE(client->desktops().count(), 2u);
 }
 
 void VirtualDesktopTest::testRemoveDesktopWithWindow_data()
@@ -282,7 +299,7 @@
     QCOMPARE(VirtualDesktopManager::self()->currentDesktop(), client->desktops().first());
 
     //Set the window on desktop 2 as well
-    client->setDesktop(2u);
+    client->enterDesktop(VirtualDesktopManager::self()->desktops()[1]);
     QCOMPARE(client->desktops().count(), 2u);
     QCOMPARE(VirtualDesktopManager::self()->desktops()[2], client->desktops()[0]);
     QCOMPARE(VirtualDesktopManager::self()->desktops()[1], client->desktops()[1]);
@@ -298,8 +315,8 @@
     //Again 3 desktops
     VirtualDesktopManager::self()->setCount(3);
     //move window to be only on desktop 3
-    client->setDesktop(3);
-    client->unSetDesktop(2);
+    client->enterDesktop(VirtualDesktopManager::self()->desktops()[2]);
+    client->leaveDesktop(VirtualDesktopManager::self()->desktops()[1]);
     QCOMPARE(client->desktops().count(), 1u);
     //window is only on desktop 3
     QCOMPARE(VirtualDesktopManager::self()->desktops()[2], client->desktops()[0]);
diff --git a/autotests/mock_effectshandler.h b/autotests/mock_effectshandler.h
--- a/autotests/mock_effectshandler.h
+++ b/autotests/mock_effectshandler.h
@@ -263,6 +263,11 @@
     }
     void hideOnScreenMessage(OnScreenMessageHideFlags flags = OnScreenMessageHideFlags()) override { Q_UNUSED(flags)}
 
+    void windowToDesktops(KWin::EffectWindow *w, const QVector<uint> &desktops) {
+        Q_UNUSED(w)
+        Q_UNUSED(desktops)
+    }
+
     KSharedConfigPtr config() const override;
     KSharedConfigPtr inputConfig() const override;
 
diff --git a/effects.h b/effects.h
--- a/effects.h
+++ b/effects.h
@@ -260,6 +260,8 @@
         return registered_atoms.contains(atom);
     }
 
+    void windowToDesktops(EffectWindow *w, const QVector<uint> &desktops);
+
 public Q_SLOTS:
     void slotCurrentTabAboutToChange(EffectWindow* from, EffectWindow* to);
     void slotTabAdded(EffectWindow* from, EffectWindow* to);
diff --git a/effects.cpp b/effects.cpp
--- a/effects.cpp
+++ b/effects.cpp
@@ -916,6 +916,28 @@
     }
 }
 
+void EffectsHandlerImpl::windowToDesktops(EffectWindow *w, const QVector<uint> &desktopIds)
+{
+    AbstractClient* cl = qobject_cast< AbstractClient* >(static_cast<EffectWindowImpl*>(w)->window());
+    if (!cl || cl->isDesktop() || cl->isDock()) {
+        return;
+    }
+    QVector<VirtualDesktop*> desktops;
+    desktops.reserve(desktopIds.count());
+    for (uint x11Id: desktopIds) {
+        if (x11Id > VirtualDesktopManager::self()->count()) {
+            continue;
+        }
+        VirtualDesktop *d = VirtualDesktopManager::self()->desktopForX11Id(x11Id);
+        Q_ASSERT(d);
+        if (desktops.contains(d)) {
+            continue;
+        }
+        desktops << d;
+    }
+    cl->setDesktops(desktops);
+}
+
 void EffectsHandlerImpl::windowToScreen(EffectWindow* w, int screen)
 {
     AbstractClient* cl = dynamic_cast< AbstractClient* >(static_cast<EffectWindowImpl*>(w)->window());
diff --git a/effects/desktopgrid/desktopgrid.cpp b/effects/desktopgrid/desktopgrid.cpp
--- a/effects/desktopgrid/desktopgrid.cpp
+++ b/effects/desktopgrid/desktopgrid.cpp
@@ -525,10 +525,14 @@
                     effects->defineCursor(Qt::ClosedHandCursor);
                 }
                 if (d != highlightedDesktop) {
-                    effects->windowToDesktop(windowMove, d);   // Not true all desktop move
+                    auto desktops = windowMove->desktops();
+                    if (!desktops.contains(d)) {
+                        desktops.append(d);
+                    }
                     if (highlightedDesktop != sourceDesktop || !wasWindowCopy) {
-                        effects->removeWindowFromDesktop(windowMove, highlightedDesktop);
+                        desktops.removeOne(highlightedDesktop);
                     }
+                    effects->windowToDesktops(windowMove, desktops);
                     const int screen = effects->screenNumber(me->pos());
                     if (screen != windowMove->screen())
                         effects->windowToScreen(windowMove, screen);
@@ -561,8 +565,10 @@
                     if (desks[i] == desks[i+1])
                         continue;
                     foreach (EffectWindow *w, stack[i]) {
-                        effects->windowToDesktop(w, desks[i+1]);
-                        effects->removeWindowFromDesktop(w, desks[i]);
+                        auto desktops = w->desktops();
+                        desktops.removeOne(desks[i]);
+                        desktops.append(desks[i+1]);
+                        effects->windowToDesktops(w, desktops);
 
                         if (isUsingPresentWindows()) {
                             m_managers[(desks[i]-1)*(effects->numScreens()) + w->screen()].unmanage(w);
diff --git a/libkwineffects/kwineffects.h b/libkwineffects/kwineffects.h
--- a/libkwineffects/kwineffects.h
+++ b/libkwineffects/kwineffects.h
@@ -943,15 +943,25 @@
     virtual void activateWindow(KWin::EffectWindow* c) = 0;
     virtual KWin::EffectWindow* activeWindow() const = 0 ;
     Q_SCRIPTABLE virtual void moveWindow(KWin::EffectWindow* w, const QPoint& pos, bool snap = false, double snapAdjust = 1.0) = 0;
+
+    /**
+     * Moves the window to the specific desktop
+     * Setting desktop to NET::OnAllDesktops will set the window on all desktops
+     */
     Q_SCRIPTABLE virtual void windowToDesktop(KWin::EffectWindow* w, int desktop) = 0;
+
     /**
-     * Removes a window from a desktop on wayland, no-op on X11
+     * Moves a window to the given desktops
+     * On X11, the window will end up on the last window in the list
+     * Setting this to an empty list will set the window on all desktops
+     *
+     * @arg desktopIds a list of desktops the window should be placed on. NET::OnAllDesktops is not a valid desktop X11Id
      */
-    Q_SCRIPTABLE void removeWindowFromDesktop(KWin::EffectWindow* w, int desktop);
+    Q_SCRIPTABLE virtual void windowToDesktops(KWin::EffectWindow* w, const QVector<uint> &desktopIds) = 0;
+
     Q_SCRIPTABLE virtual void windowToScreen(KWin::EffectWindow* w, int screen) = 0;
     virtual void setShowingDesktop(bool showing) = 0;
 
-
     // Activities
     /**
      * @returns The ID of the current activity.
@@ -2091,7 +2101,7 @@
      * a length of 1, on Wayland can be any subset.
      * If the list is empty it means the window is on all desktops
      */
-    QVector<int> desktops() const;
+    QVector<uint> desktops() const;
 
     int x() const;
     int y() const;
diff --git a/libkwineffects/kwineffects.cpp b/libkwineffects/kwineffects.cpp
--- a/libkwineffects/kwineffects.cpp
+++ b/libkwineffects/kwineffects.cpp
@@ -762,13 +762,6 @@
     return compositing_type & OpenGLCompositing;
 }
 
-void EffectsHandler::removeWindowFromDesktop(KWin::EffectWindow* w, int desktop)
-{
-    if (w->parent() && !w->isDesktop() && !w->isDock()) {
-        QMetaObject::invokeMethod(w->parent(), "unSetDesktop", Q_ARG(int, desktop));
-    }
-}
-
 EffectsHandler* effects = nullptr;
 
 
@@ -855,7 +848,7 @@
 WINDOW_HELPER(QStringList, activities, "activities")
 WINDOW_HELPER(bool, skipsCloseAnimation, "skipsCloseAnimation")
 WINDOW_HELPER(KWayland::Server::SurfaceInterface *, surface, "surface")
-WINDOW_HELPER(QVector<int>, desktops, "x11DesktopIds")
+WINDOW_HELPER(QVector<uint>, desktops, "x11DesktopIds")
 WINDOW_HELPER(bool, isPopupWindow, "popupWindow")
 
 QString EffectWindow::windowClass() const
@@ -983,7 +976,7 @@
 
 bool EffectWindow::isOnDesktop(int d) const
 {
-    const QVector<int> ds = desktops();
+    const QVector<uint> ds = desktops();
     return ds.isEmpty() || ds.contains(d);
 }
 
diff --git a/useractions.cpp b/useractions.cpp
--- a/useractions.cpp
+++ b/useractions.cpp
@@ -900,7 +900,6 @@
         return;
     }
 
-    Workspace *ws = Workspace::self();
     VirtualDesktopManager *vds = VirtualDesktopManager::self();
     if (desk == 0) {
         // the 'on_all_desktops' menu entry
@@ -912,9 +911,9 @@
 
     VirtualDesktop *virtualDesktop = VirtualDesktopManager::self()->desktopForX11Id(desk);
     if (m_client.data()->desktops().contains(virtualDesktop)) {
-        m_client.data()->unSetDesktop(desk);
+        m_client.data()->leaveDesktop(virtualDesktop);
     } else {
-        ws->sendClientToDesktop(m_client.data(), desk, false);
+        m_client.data()->enterDesktop(virtualDesktop);
     }
 }