diff --git a/src/core/desktopexecparser.cpp b/src/core/desktopexecparser.cpp
--- a/src/core/desktopexecparser.cpp
+++ b/src/core/desktopexecparser.cpp
@@ -421,7 +421,15 @@
     if (d->service.terminal()) {
         KConfigGroup cg(KSharedConfig::openConfig(), "General");
         QString terminal = cg.readPathEntry("TerminalApplication", QStringLiteral("konsole"));
-        if (terminal == QLatin1String("konsole")) {
+        const bool isKonsole = (terminal == QLatin1String("konsole"));
+
+        QString terminalPath = QStandardPaths::findExecutable(terminal);
+        if (terminalPath.isEmpty()) {
+            qCWarning(KIO_CORE) << "Terminal" << terminal << "not found, service" << d->service.name();
+            return QStringList();
+        }
+        terminal = terminalPath;
+        if (isKonsole) {
             if (!d->service.workingDirectory().isEmpty()) {
                 terminal += QLatin1String(" --workdir ") + KShell::quoteArg(d->service.workingDirectory());
             }
diff --git a/src/gui/kprocessrunner.cpp b/src/gui/kprocessrunner.cpp
--- a/src/gui/kprocessrunner.cpp
+++ b/src/gui/kprocessrunner.cpp
@@ -88,9 +88,17 @@
         emitDelayedError(i18n("The desktop entry file\n%1\nis not valid.", service->entryPath()));
         return;
     }
+
     KIO::DesktopExecParser execParser(*service, urls);
+    execParser.setUrlsAreTempFiles(flags & KIO::ApplicationLauncherJob::DeleteTemporaryFiles);
+    execParser.setSuggestedFileName(suggestedFileName);
+    const QStringList args = execParser.resultingArguments();
+    if (args.isEmpty()) {
+        emitDelayedError(i18n("Error processing Exec field in %1", service->entryPath()));
+        return;
+    }
 
-    const QString realExecutable = execParser.resultingArguments().at(0);
+    const QString realExecutable = args.at(0);
     // realExecutable is a full path if DesktopExecParser was able to locate it. Otherwise it's still relative, which is a bad sign.
     if (QDir::isRelativePath(realExecutable) || !QFileInfo(realExecutable).isExecutable()) {
         // Does it really not exist, or is it non-executable? (bug #415567)
@@ -103,13 +111,6 @@
         return;
     }
 
-    execParser.setUrlsAreTempFiles(flags & KIO::ApplicationLauncherJob::DeleteTemporaryFiles);
-    execParser.setSuggestedFileName(suggestedFileName);
-    const QStringList args = execParser.resultingArguments();
-    if (args.isEmpty()) {
-        emitDelayedError(i18n("Error processing Exec field in %1", service->entryPath()));
-        return;
-    }
     //qDebug() << "KProcess args=" << args;
     *m_process << args;