diff --git a/autotests/applicationlauncherjobtest.cpp b/autotests/applicationlauncherjobtest.cpp
--- a/autotests/applicationlauncherjobtest.cpp
+++ b/autotests/applicationlauncherjobtest.cpp
@@ -156,21 +156,29 @@
 void ApplicationLauncherJobTest::shouldFailOnNonExistingExecutable_data()
 {
     QTest::addColumn<bool>("tempFile");
+    QTest::addColumn<bool>("fullPath");
 
-    QTest::newRow("file") << false;
-    QTest::newRow("tempFile") << true;
+    QTest::newRow("file") << false << false;
+    QTest::newRow("tempFile") << true << false;
+    QTest::newRow("file_fullPath") << false << true;
+    QTest::newRow("tempFile_fullPath") << true << true;
 }
 
 void ApplicationLauncherJobTest::shouldFailOnNonExistingExecutable()
 {
     QFETCH(bool, tempFile);
+    QFETCH(bool, fullPath);
 
     const QString desktopFilePath = QStandardPaths::writableLocation(QStandardPaths::GenericDataLocation) + QLatin1String("/kservices5/non_existing_executable.desktop");
     KDesktopFile file(desktopFilePath);
     KConfigGroup group = file.desktopGroup();
     group.writeEntry("Name", "KRunUnittestService");
     group.writeEntry("Type", "Service");
-    group.writeEntry("Exec", "does_not_exist %f %d/dest_%n");
+    if (fullPath) {
+        group.writeEntry("Exec", "/usr/bin/does_not_exist %f %d/dest_%n");
+    } else {
+        group.writeEntry("Exec", "does_not_exist %f %d/dest_%n");
+    }
     file.sync();
 
     KService::Ptr servicePtr(new KService(desktopFilePath));
@@ -181,8 +189,11 @@
     }
     QVERIFY(!job->exec());
     QCOMPARE(job->error(), KJob::UserDefinedError);
-    QCOMPARE(job->errorString(), QStringLiteral("Could not find the program 'does_not_exist'"));
-
+    if (fullPath) {
+        QCOMPARE(job->errorString(), QStringLiteral("Could not find the program '/usr/bin/does_not_exist'"));
+    } else {
+        QCOMPARE(job->errorString(), QStringLiteral("Could not find the program 'does_not_exist'"));
+    }
     QFile::remove(desktopFilePath);
 }
 
diff --git a/src/core/desktopexecparser.cpp b/src/core/desktopexecparser.cpp
--- a/src/core/desktopexecparser.cpp
+++ b/src/core/desktopexecparser.cpp
@@ -443,14 +443,17 @@
     KShell::Errors err;
     QStringList execlist = KShell::splitArgs(exec, KShell::AbortOnMeta | KShell::TildeExpand, &err);
     if (err == KShell::NoError && !execlist.isEmpty()) { // mx1 checked for syntax errors already
-        // Resolve the executable to ensure that helpers in libexec are found.
-        // Too bad for commands that need a shell - they must reside in $PATH.
-        QString exePath = QStandardPaths::findExecutable(execlist.first());
-        if (exePath.isEmpty()) {
-            exePath = QFile::decodeName(CMAKE_INSTALL_FULL_LIBEXECDIR_KF5 "/") + execlist.first();
-        }
-        if (QFile::exists(exePath)) {
-            execlist[0] = exePath;
+        const QString executable = execlist.at(0);
+        if (QDir::isRelativePath(executable)) {
+            // Resolve the executable to ensure that helpers in libexec are found.
+            // Too bad for commands that need a shell - they must reside in $PATH.
+            QString exePath = QStandardPaths::findExecutable(executable);
+            if (exePath.isEmpty()) {
+                exePath = QFile::decodeName(CMAKE_INSTALL_FULL_LIBEXECDIR_KF5 "/") + executable;
+            }
+            if (QFile::exists(exePath)) {
+                execlist[0] = exePath;
+            }
         }
     }
     if (d->service.substituteUid()) {
diff --git a/src/gui/kprocessrunner.cpp b/src/gui/kprocessrunner.cpp
--- a/src/gui/kprocessrunner.cpp
+++ b/src/gui/kprocessrunner.cpp
@@ -35,15 +35,48 @@
 #include <QDBusMetaType>
 #include <QDBusPendingCallWatcher>
 #include <QDBusReply>
+#include <QDir>
 #include <QFileInfo>
 #include <QGuiApplication>
 #include <QStandardPaths>
+#include <QString>
 #include <QUuid>
 
 #include <mutex>
 
 static int s_instanceCount = 0; // for the unittest
 
+static QString findNonExecutableProgram(const QString &executable)
+{
+    // Relative to current dir, or absolute path
+    const QFileInfo fi(executable);
+    if (fi.exists() && !fi.isExecutable()) {
+        return executable;
+    }
+
+#ifdef Q_OS_UNIX
+    // This is a *very* simplified version of QStandardPaths::findExecutable
+#if QT_VERSION < QT_VERSION_CHECK(5, 15, 0)
+    const auto skipEmptyParts = QString::SkipEmptyParts;
+#else
+    const auto skipEmptyParts = Qt::SkipEmptyParts;
+#endif
+    const QStringList searchPaths = QString::fromLocal8Bit(qgetenv("PATH")).split(QDir::listSeparator(), skipEmptyParts);
+    for (const QString &searchPath : searchPaths) {
+        const QString candidate = searchPath + QLatin1Char('/') + executable;
+        const QFileInfo fileInfo(candidate);
+        if (fileInfo.exists()) {
+            if (fileInfo.isExecutable()) {
+                qWarning() << "Internal program error. QStandardPaths::findExecutable couldn't find" << executable << "but our own logic found it at" << candidate << ". Please report a bug at https://bugs.kde.org";
+            } else {
+                return candidate;
+            }
+        }
+    }
+#endif
+    return QString();
+}
+
 KProcessRunner::KProcessRunner(const KService::Ptr &service, const QList<QUrl> &urls,
                                KIO::ApplicationLauncherJob::RunFlags flags, const QString &suggestedFileName, const QByteArray &asn)
     : m_process{new KProcess},
@@ -53,8 +86,15 @@
     KIO::DesktopExecParser execParser(*service, urls);
 
     const QString realExecutable = execParser.resultingArguments().at(0);
-    if (!QFileInfo::exists(realExecutable) && QStandardPaths::findExecutable(realExecutable).isEmpty()) {
-        emitDelayedError(i18n("Could not find the program '%1'", realExecutable));
+    // 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)
+        const QString nonExecutable = findNonExecutableProgram(realExecutable);
+        if (nonExecutable.isEmpty()) {
+            emitDelayedError(i18n("Could not find the program '%1'", realExecutable));
+        } else {
+            emitDelayedError(i18n("The program '%1' was found at '%2' but it is missing executable permissions.", realExecutable, nonExecutable));
+        }
         return;
     }