diff --git a/src/os_mswin.c b/src/os_mswin.c
index 57ac582..fb9a3be 100644
--- a/src/os_mswin.c
+++ b/src/os_mswin.c
@@ -440,6 +440,27 @@
 #define _fstat _fstat64
 
     static int
+read_reparse_point(const WCHAR *name, char_u *buf, DWORD *buf_len)
+{
+    HANDLE h;
+    BOOL ok;
+
+    h = CreateFileW(name, FILE_READ_ATTRIBUTES,
+	    FILE_SHARE_READ | FILE_SHARE_WRITE, NULL,
+	    OPEN_EXISTING,
+	    FILE_FLAG_BACKUP_SEMANTICS | FILE_FLAG_OPEN_REPARSE_POINT,
+	    NULL);
+    if (h == INVALID_HANDLE_VALUE)
+	return FAIL;
+
+    ok = DeviceIoControl(h, FSCTL_GET_REPARSE_POINT, NULL, 0, buf, *buf_len,
+	    buf_len, NULL);
+    CloseHandle(h);
+
+    return ok ? OK : FAIL;
+}
+
+    static int
 wstat_symlink_aware(const WCHAR *name, stat_T *stp)
 {
 #if (defined(_MSC_VER) && (_MSC_VER < 1900)) || defined(__MINGW32__)
@@ -491,6 +512,61 @@
     return _wstat(name, (struct _stat *)stp);
 }
 
+    char_u *
+resolve_appexeclink(char_u *fname)
+{
+    DWORD	        attr = 0;
+    int	                idx;
+    WCHAR	        *p, *end, *wname;
+    // The buffer size is arbitrarily chosen to be "big enough" (TM), the
+    // ceiling should be around 16k.
+    char_u	        buf[4096];
+    DWORD	        buf_len = sizeof(buf);
+    REPARSE_DATA_BUFFER *rb = (REPARSE_DATA_BUFFER *)buf;
+
+    wname = enc_to_utf16(fname, NULL);
+    if (wname == NULL)
+	return NULL;
+
+    attr = GetFileAttributesW(wname);
+    if (attr == INVALID_FILE_ATTRIBUTES ||
+	    (attr & FILE_ATTRIBUTE_REPARSE_POINT) == 0)
+    {
+	vim_free(wname);
+	return NULL;
+    }
+
+    // The applinks are similar to symlinks but with a huge difference: they can
+    // only be executed, any other I/O operation on them is bound to fail with
+    // ERROR_FILE_NOT_FOUND even though the file exists.
+    if (read_reparse_point(wname, buf, &buf_len) == FAIL)
+    {
+	vim_free(wname);
+	return NULL;
+    }
+    vim_free(wname);
+
+    if (rb->ReparseTag != IO_REPARSE_TAG_APPEXECLINK)
+	return NULL;
+
+    // The (undocumented) reparse buffer contains a set of N null-terminated
+    // Unicode strings, the application path is stored in the third one.
+    if (rb->AppExecLinkReparseBuffer.StringCount < 3)
+	return NULL;
+
+    p = rb->AppExecLinkReparseBuffer.StringList;
+    end = p + rb->ReparseDataLength / sizeof(WCHAR);
+    for (idx = 0; p < end
+	    && idx < (int)rb->AppExecLinkReparseBuffer.StringCount
+	    && idx != 2; )
+    {
+	if ((*p++ == L'\0'))
+	    ++idx;
+    }
+
+    return utf16_to_enc(p, NULL);
+}
+
 /*
  * stat() can't handle a trailing '/' or '\', remove it first.
  */
diff --git a/src/os_win32.c b/src/os_win32.c
index 97595d6..7224fad 100644
--- a/src/os_win32.c
+++ b/src/os_win32.c
@@ -2127,13 +2127,27 @@
     static int
 executable_file(char *name, char_u **path)
 {
-    if (mch_getperm((char_u *)name) != -1 && !mch_isdir((char_u *)name))
+    int attrs = win32_getattrs((char_u *)name);
+
+    // The file doesn't exist or is a folder.
+    if (attrs == -1 || (attrs & FILE_ATTRIBUTE_DIRECTORY))
+	return FALSE;
+    // Check if the file is an AppExecLink, a special alias used by Windows
+    // Store for its apps.
+    if (attrs & FILE_ATTRIBUTE_REPARSE_POINT)
     {
+	char_u	*res = resolve_appexeclink((char_u *)name);
+	if (res == NULL)
+	    return FALSE;
+	// The path is already absolute.
 	if (path != NULL)
-	    *path = FullName_save((char_u *)name, FALSE);
-	return TRUE;
+	    *path = res;
+	else
+	    vim_free(res);
     }
-    return FALSE;
+    else if (path != NULL)
+	*path = FullName_save((char_u *)name, FALSE);
+    return TRUE;
 }
 
 /*
diff --git a/src/os_win32.h b/src/os_win32.h
index 4643570..a98951e 100644
--- a/src/os_win32.h
+++ b/src/os_win32.h
@@ -126,6 +126,45 @@
 #ifndef IO_REPARSE_TAG_SYMLINK
 # define IO_REPARSE_TAG_SYMLINK		0xA000000C
 #endif
+#ifndef IO_REPARSE_TAG_APPEXECLINK
+# define IO_REPARSE_TAG_APPEXECLINK	0x8000001B
+#endif
+
+/*
+ * Definition of the reparse point buffer.
+ * This is usually defined in the DDK, copy the definition here to avoid
+ * adding it as a dependence only for a single structure.
+ */
+typedef struct _REPARSE_DATA_BUFFER {
+    ULONG  ReparseTag;
+    USHORT ReparseDataLength;
+    USHORT Reserved;
+    union {
+	struct {
+	    USHORT SubstituteNameOffset;
+	    USHORT SubstituteNameLength;
+	    USHORT PrintNameOffset;
+	    USHORT PrintNameLength;
+	    ULONG  Flags;
+	    WCHAR  PathBuffer[1];
+	} SymbolicLinkReparseBuffer;
+	struct {
+	    USHORT SubstituteNameOffset;
+	    USHORT SubstituteNameLength;
+	    USHORT PrintNameOffset;
+	    USHORT PrintNameLength;
+	    WCHAR  PathBuffer[1];
+	} MountPointReparseBuffer;
+	struct {
+	    UCHAR DataBuffer[1];
+	} GenericReparseBuffer;
+	struct
+	{
+	    ULONG StringCount;
+	    WCHAR StringList[1];
+	} AppExecLinkReparseBuffer;
+    } DUMMYUNIONNAME;
+} REPARSE_DATA_BUFFER, *PREPARSE_DATA_BUFFER;
 
 #ifdef _MSC_VER
     // Support for __try / __except.  All versions of MSVC are
diff --git a/src/proto/os_mswin.pro b/src/proto/os_mswin.pro
index e8a6cb9..e3c5b60 100644
--- a/src/proto/os_mswin.pro
+++ b/src/proto/os_mswin.pro
@@ -50,4 +50,5 @@
 char *quality_id2name(DWORD id);
 int get_logfont(LOGFONTW *lf, char_u *name, HDC printer_dc, int verbose);
 void channel_init_winsock(void);
+char_u *resolve_appexeclink(char_u *fname);
 /* vim: set ft=c : */
diff --git a/src/testdir/test_functions.vim b/src/testdir/test_functions.vim
index 87b3844..9eae10d 100644
--- a/src/testdir/test_functions.vim
+++ b/src/testdir/test_functions.vim
@@ -1398,6 +1398,28 @@
   endif
 endfunc
 
+func Test_executable_windows_store_apps()
+  CheckMSWindows
+
+  " Windows Store apps install some 'decoy' .exe that require some careful
+  " handling as they behave similarly to symlinks.
+  let app_dir = expand("$LOCALAPPDATA\\Microsoft\\WindowsApps")
+  if !isdirectory(app_dir)
+    return
+  endif
+
+  let save_path = $PATH
+  let $PATH = app_dir
+  " Ensure executable() finds all the app .exes
+  for entry in readdir(app_dir)
+    if entry =~ '\.exe$'
+      call assert_true(executable(entry))
+    endif
+  endfor
+
+  let $PATH = save_path
+endfunc
+
 func Test_executable_longname()
   CheckMSWindows
 
diff --git a/src/version.c b/src/version.c
index 33e2a5f..59df1ad 100644
--- a/src/version.c
+++ b/src/version.c
@@ -747,6 +747,8 @@
 static int included_patches[] =
 {   /* Add new patch number below this line */
 /**/
+    4875,
+/**/
     4874,
 /**/
     4873,