diff --git a/libdiscover/backends/PackageKitBackend/PackageKitBackend.cpp b/libdiscover/backends/PackageKitBackend/PackageKitBackend.cpp
--- a/libdiscover/backends/PackageKitBackend/PackageKitBackend.cpp
+++ b/libdiscover/backends/PackageKitBackend/PackageKitBackend.cpp
@@ -583,6 +583,11 @@
         return;
     }
 
+    if (info == PackageKit::Transaction::InfoRemoving || info == PackageKit::Transaction::InfoObsoleting) {
+        // Don't try updating packages which need to be removed
+        return;
+    }
+
     if (info == PackageKit::Transaction::InfoSecurity)
         m_hasSecurityUpdates = true;