diff --git a/src/kmcommands.h b/src/kmcommands.h
--- a/src/kmcommands.h
+++ b/src/kmcommands.h
@@ -558,16 +558,48 @@
     MessageList::Core::MessageItemSetReference mRef;
 };
 
-class KMTrashMsgCommand : public KMMoveCommand
+class KMTrashMsgCommand final : public KMCommand
 {
     Q_OBJECT
 
 public:
+    enum TrashOperation {
+        Unknown,
+        MoveToTrash,
+        Delete,
+        Both
+    };
+
     KMTrashMsgCommand(const Akonadi::Collection &srcFolder, const Akonadi::Item::List &msgList, MessageList::Core::MessageItemSetReference ref);
     KMTrashMsgCommand(const Akonadi::Collection &srcFolder, const Akonadi::Item &msg, MessageList::Core::MessageItemSetReference ref);
+    MessageList::Core::MessageItemSetReference refSet() const
+    {
+        return mRef;
+    }
+
+    TrashOperation operation() const;
+
+public Q_SLOTS:
+    void slotMoveCanceled();
+
+private Q_SLOTS:
+    void slotMoveResult(KJob *job);
+    void slotDeleteResult(KJob *job);
+Q_SIGNALS:
+    void moveDone(KMTrashMsgCommand *);
 
 private:
+    Result execute() override;
+    void completeMove(Result result);
+
     static Akonadi::Collection findTrashFolder(const Akonadi::Collection &srcFolder);
+
+    QMap<Akonadi::Collection, Akonadi::Item::List> mTrashFolders;
+    KPIM::ProgressItem *mMoveProgress = nullptr;
+    KPIM::ProgressItem *mDeleteProgress = nullptr;
+    MessageList::Core::MessageItemSetReference mRef;
+    QList<KJob*> mPendingMoves;
+    QList<KJob*> mPendingDeletes;
 };
 
 class KMResendMessageCommand : public KMCommand
diff --git a/src/kmcommands.cpp b/src/kmcommands.cpp
--- a/src/kmcommands.cpp
+++ b/src/kmcommands.cpp
@@ -1563,17 +1563,55 @@
     completeMove(Canceled);
 }
 
-// srcFolder doesn't make much sense for searchFolders
 KMTrashMsgCommand::KMTrashMsgCommand(const Akonadi::Collection &srcFolder, const Akonadi::Item::List &msgList, MessageList::Core::MessageItemSetReference ref)
-    : KMMoveCommand(findTrashFolder(srcFolder), msgList, ref)
+    : KMCommand()
+    , mRef(ref)
 {
+    // When trashing items from a virtual collection, they may each have a different
+    // trash folder, so we need to handle it here carefuly
+    if (srcFolder.isVirtual()) {
+        QHash<qint64, Akonadi::Collection> cache;
+        for (const auto &msg : msgList) {
+            auto cacheIt = cache.find(msg.storageCollectionId());
+            if (cacheIt == cache.end()) {
+                cacheIt = cache.insert(msg.storageCollectionId(), findTrashFolder(CommonKernel->collectionFromId(msg.storageCollectionId())));
+            }
+            auto trashIt = mTrashFolders.find(*cacheIt);
+            if (trashIt == mTrashFolders.end()) {
+                trashIt = mTrashFolders.insert(*cacheIt, {});
+            }
+            trashIt->push_back(msg);
+        }
+    } else {
+        mTrashFolders.insert(findTrashFolder(srcFolder), msgList);
+    }
 }
 
-KMTrashMsgCommand::KMTrashMsgCommand(const Akonadi::Collection &srcFolder, const Akonadi::Item &msg, MessageList::Core::MessageItemSetReference ref)
-    : KMMoveCommand(findTrashFolder(srcFolder), msg, ref)
+KMTrashMsgCommand::TrashOperation KMTrashMsgCommand::operation() const
 {
+    if (!mPendingMoves.isEmpty() && !mPendingDeletes.isEmpty()) {
+        return Both;
+    } else if (!mPendingMoves.isEmpty()) {
+        return MoveToTrash;
+    } else if (!mPendingDeletes.isEmpty()) {
+        return Delete;
+    } else {
+        if (mTrashFolders.size() == 1) {
+            if (mTrashFolders.begin().key().isValid()) {
+                return MoveToTrash;
+            } else {
+                return Delete;
+            }
+        } else {
+            return Unknown;
+        }
+    }
 }
 
+KMTrashMsgCommand::KMTrashMsgCommand(const Akonadi::Collection &srcFolder, const Akonadi::Item &msg, MessageList::Core::MessageItemSetReference ref)
+    : KMTrashMsgCommand(findTrashFolder(srcFolder), Akonadi::Item::List{msg}, ref)
+{}
+
 Akonadi::Collection KMTrashMsgCommand::findTrashFolder(const Akonadi::Collection &folder)
 {
     Akonadi::Collection col = CommonKernel->trashCollectionFromResource(folder);
@@ -1586,6 +1624,124 @@
     return Akonadi::Collection();
 }
 
+KMCommand::Result KMTrashMsgCommand::execute()
+{
+#ifndef QT_NO_CURSOR
+    KPIM::KCursorSaver busy(KPIM::KBusyPtr::busy());
+#endif
+    setEmitsCompletedItself(true);
+    setDeletesItself(true);
+    for (auto trashIt = mTrashFolders.begin(), end = mTrashFolders.end(); trashIt != end; ++trashIt) {
+        const auto trash = trashIt.key();
+        if (trash.isValid()) {
+            Akonadi::ItemMoveJob *job = new Akonadi::ItemMoveJob(*trashIt, trash, this);
+            connect(job, &KIO::Job::result, this, &KMTrashMsgCommand::slotMoveResult);
+            mPendingMoves.push_back(job);
+
+            // group by source folder for undo
+            std::sort(trashIt->begin(), trashIt->end(),
+                      [](const Akonadi::Item &lhs, const Akonadi::Item &rhs) {
+                return lhs.storageCollectionId() < rhs.storageCollectionId();
+            });
+            Akonadi::Collection parent;
+            int undoId = -1;
+            for (const Akonadi::Item &item : qAsConst(*trashIt)) {
+                if (item.storageCollectionId() <= 0) {
+                    continue;
+                }
+                if (parent.id() != item.storageCollectionId()) {
+                    parent = Akonadi::Collection(item.storageCollectionId());
+                    undoId = kmkernel->undoStack()->newUndoAction(parent, trash);
+                }
+                kmkernel->undoStack()->addMsgToAction(undoId, item);
+            }
+        } else {
+            Akonadi::ItemDeleteJob *job = new Akonadi::ItemDeleteJob(*trashIt, this);
+            connect(job, &KIO::Job::result, this, &KMTrashMsgCommand::slotDeleteResult);
+            mPendingDeletes.push_back(job);
+        }
+    }
+
+    if (mPendingMoves.isEmpty() && mPendingDeletes.isEmpty()) {
+        deleteLater();
+        return Failed;
+    }
+
+    // TODO set SSL state according to source and destfolder connection?
+    if (!mPendingMoves.isEmpty()) {
+        Q_ASSERT(!mMoveProgress);
+        mMoveProgress = ProgressManager::createProgressItem(QLatin1String("move") + ProgressManager::getUniqueID(),
+            i18n("Moving messages"), QString(), true, KPIM::ProgressItem::Unknown);
+        mMoveProgress->setUsesBusyIndicator(true);
+        connect(mMoveProgress, &ProgressItem::progressItemCanceled,
+                this, &KMTrashMsgCommand::slotMoveCanceled);
+    }
+    if (!mPendingDeletes.isEmpty()) {
+        Q_ASSERT(!mDeleteProgress);
+        mDeleteProgress = ProgressManager::createProgressItem(QLatin1String("delete") + ProgressManager::getUniqueID(),
+            i18n("Deleting messages"), QString(), true, KPIM::ProgressItem::Unknown);
+        mDeleteProgress->setUsesBusyIndicator(true);
+        connect(mMoveProgress, &ProgressItem::progressItemCanceled,
+                this, &KMTrashMsgCommand::slotMoveCanceled);
+    }
+    return OK;
+}
+
+void KMTrashMsgCommand::slotMoveResult(KJob *job)
+{
+    mPendingMoves.removeOne(job);
+    if (job->error()) {
+        // handle errors
+        showJobError(job);
+        completeMove(Failed);
+    } else if (mPendingMoves.isEmpty() && mPendingDeletes.isEmpty()) {
+        completeMove(OK);
+    }
+}
+
+void KMTrashMsgCommand::slotDeleteResult(KJob* job)
+{
+    mPendingDeletes.removeOne(job);
+    if (job->error()) {
+        showJobError(job);
+        completeMove(Failed);
+    } else if (mPendingDeletes.isEmpty() && mPendingMoves.isEmpty()) {
+        completeMove(OK);
+    }
+}
+
+void KMTrashMsgCommand::slotMoveCanceled()
+{
+    completeMove(Canceled);
+}
+
+void KMTrashMsgCommand::completeMove(KMCommand::Result result)
+{
+    if (result == Failed) {
+        for (auto job : mPendingMoves) {
+            job->kill();
+        }
+        for (auto job : mPendingDeletes) {
+            job->kill();
+        }
+    }
+
+    if (mDeleteProgress) {
+        mDeleteProgress->setComplete();
+        mDeleteProgress = nullptr;
+    }
+    if (mMoveProgress) {
+        mMoveProgress->setComplete();
+        mMoveProgress = nullptr;
+    }
+
+    setResult(result);
+    Q_EMIT moveDone(this);
+    Q_EMIT completed(this);
+    deleteLater();
+}
+
+
 KMSaveAttachmentsCommand::KMSaveAttachmentsCommand(QWidget *parent, const Akonadi::Item &msg, MessageViewer::Viewer *viewer)
     : KMCommand(parent, msg)
     , mViewer(viewer)
diff --git a/src/kmmainwidget.h b/src/kmmainwidget.h
--- a/src/kmmainwidget.h
+++ b/src/kmmainwidget.h
@@ -60,6 +60,7 @@
 class CollectionPane;
 class KMCommand;
 class KMMoveCommand;
+class KMTrashMsgCommand;
 class KRecentFilesAction;
 class ManageShowCollectionProperties;
 class KActionMenuTransport;
@@ -469,7 +470,7 @@
     /**
      * Called when a "move to trash" operation is completed
      */
-    void slotTrashMessagesCompleted(KMMoveCommand *command);
+    void slotTrashMessagesCompleted(KMTrashMsgCommand *command);
 
     /**
      * Called when a "move" operation is completed
diff --git a/src/kmmainwidget.cpp b/src/kmmainwidget.cpp
--- a/src/kmmainwidget.cpp
+++ b/src/kmmainwidget.cpp
@@ -1845,28 +1845,66 @@
     // And stuff them into a KMTrashMsgCommand :)
     KMTrashMsgCommand *command = new KMTrashMsgCommand(mCurrentCollection, select, ref);
 
-    QObject::connect(
-        command, &KMMoveCommand::moveDone,
-        this, &KMMainWidget::slotTrashMessagesCompleted
-        );
+    QObject::connect(command, &KMTrashMsgCommand::moveDone,
+                     this, &KMMainWidget::slotTrashMessagesCompleted);
     command->start();
-    bool moveToTrash = command->destFolder().isValid();
-    showMessageActivities(moveToTrash ? i18n("Moving messages to trash...") : i18n("Deleting messages..."));
+    switch (command->operation()) {
+    case KMTrashMsgCommand::MoveToTrash:
+        showMessageActivities(i18n("Moving messages to trash..."));
+        break;
+    case KMTrashMsgCommand::Delete:
+        showMessageActivities(i18n("Deleting messages..."));
+        break;
+    case KMTrashMsgCommand::Both:
+    case KMTrashMsgCommand::Unknown:
+        showMessageActivities(i18n("Deleting and moving messages to trash..."));
+        break;
+    }
 }
 
-void KMMainWidget::slotTrashMessagesCompleted(KMMoveCommand *command)
+void KMMainWidget::slotTrashMessagesCompleted(KMTrashMsgCommand *command)
 {
     Q_ASSERT(command);
     mMessagePane->markMessageItemsAsAboutToBeRemoved(command->refSet(), false);
     mMessagePane->deletePersistentSet(command->refSet());
-    bool moveToTrash = command->destFolder().isValid();
     if (command->result() == KMCommand::OK) {
-        showMessageActivities(moveToTrash ? i18n("Messages moved to trash successfully.") : i18n("Messages deleted successfully."));
+        switch (command->operation()) {
+        case KMTrashMsgCommand::MoveToTrash:
+            showMessageActivities(i18n("Messages moved to trash successfully."));
+            break;
+        case KMTrashMsgCommand::Delete:
+            showMessageActivities(i18n("Messages deleted successfully."));
+            break;
+        case KMTrashMsgCommand::Both:
+        case KMTrashMsgCommand::Unknown:
+            showMessageActivities(i18n("Messages moved to trash or deleted successfully"));
+            break;
+        }
+    } else if (command->result() == KMCommand::Failed) {
+        switch (command->operation()) {
+        case KMTrashMsgCommand::MoveToTrash:
+            showMessageActivities(i18n("Moving messages to trash failed."));
+            break;
+        case KMTrashMsgCommand::Delete:
+            showMessageActivities(i18n("Deleting messages failed."));
+            break;
+        case KMTrashMsgCommand::Both:
+        case KMTrashMsgCommand::Unknown:
+            showMessageActivities(i18n("Deleting or moving messages to trash failed."));
+            break;
+        }
     } else {
-        if (command->result() == KMCommand::Failed) {
-            showMessageActivities(moveToTrash ? i18n("Moving messages to trash failed.") : i18n("Deleting messages failed."));
-        } else {
-            showMessageActivities(moveToTrash ? i18n("Moving messages to trash canceled.") : i18n("Deleting messages canceled."));
+        switch (command->operation()) {
+        case KMTrashMsgCommand::MoveToTrash:
+            showMessageActivities(i18n("Moving messages to trash canceled."));
+            break;
+        case KMTrashMsgCommand::Delete:
+            showMessageActivities(i18n("Deleting messages canceled."));
+            break;
+        case KMTrashMsgCommand::Both:
+        case KMTrashMsgCommand::Unknown:
+            showMessageActivities(i18n("Deleting or moving messages to trash canceled."));
+            break;
         }
     }