diff --git a/src/cmdexpand.c b/src/cmdexpand.c
index 003f6da..84dc643 100644
--- a/src/cmdexpand.c
+++ b/src/cmdexpand.c
@@ -56,7 +56,6 @@
 	    && xp->xp_context != EXPAND_FILES_IN_PATH
 	    && xp->xp_context != EXPAND_FILETYPE
 	    && xp->xp_context != EXPAND_HELP
-	    && xp->xp_context != EXPAND_MAPPINGS
 	    && xp->xp_context != EXPAND_OLD_SETTING
 	    && xp->xp_context != EXPAND_OWNSYNTAX
 	    && xp->xp_context != EXPAND_PACKADD
@@ -1216,10 +1215,12 @@
 
     // Isolate the command and search for it in the command table.
     // Exceptions:
-    // - the 'k' command can directly be followed by any character, but
-    //   do accept "keepmarks", "keepalt" and "keepjumps".
+    // - the 'k' command can directly be followed by any character, but do
+    // accept "keepmarks", "keepalt" and "keepjumps". As fuzzy matching can
+    // find matches anywhere in the command name, do this only for command
+    // expansion based on regular expression and not for fuzzy matching.
     // - the 's' command can be followed directly by 'c', 'g', 'i', 'I' or 'r'
-    if (*cmd == 'k' && cmd[1] != 'e')
+    if (!fuzzy && (*cmd == 'k' && cmd[1] != 'e'))
     {
 	eap->cmdidx = CMD_k;
 	p = cmd + 1;
@@ -2596,7 +2597,7 @@
 	    || xp->xp_context == EXPAND_BOOL_SETTINGS)
 	ret = ExpandSettings(xp, &regmatch, pat, numMatches, matches);
     else if (xp->xp_context == EXPAND_MAPPINGS)
-	ret = ExpandMappings(&regmatch, numMatches, matches);
+	ret = ExpandMappings(pat, &regmatch, numMatches, matches);
 # if defined(FEAT_EVAL)
     else if (xp->xp_context == EXPAND_USER_DEFINED)
 	ret = ExpandUserDefined(xp, &regmatch, matches, numMatches);
@@ -2712,7 +2713,8 @@
 		fuzmatch = ALLOC_MULT(fuzmatch_str_T, count);
 	    else
 		*matches = ALLOC_MULT(char_u *, count);
-	    if ((fuzzy && (fuzmatch == NULL)) || (*matches == NULL))
+	    if ((!fuzzy && (*matches == NULL))
+					|| (fuzzy && (fuzmatch == NULL)))
 	    {
 		*numMatches = 0;
 		*matches = NULL;
diff --git a/src/map.c b/src/map.c
index b681d2f..594c934 100644
--- a/src/map.c
+++ b/src/map.c
@@ -1257,9 +1257,10 @@
  */
     int
 ExpandMappings(
+    char_u	*pat,
     regmatch_T	*regmatch,
-    int		*num_file,
-    char_u	***file)
+    int		*numMatches,
+    char_u	***matches)
 {
     mapblock_T	*mp;
     int		hash;
@@ -1267,11 +1268,17 @@
     int		round;
     char_u	*p;
     int		i;
+    int		fuzzy;
+    int		match;
+    int		score;
+    fuzmatch_str_T  *fuzmatch = NULL;
+
+    fuzzy = cmdline_fuzzy_complete(pat);
 
     validate_maphash();
 
-    *num_file = 0;		    // return values in case of FAIL
-    *file = NULL;
+    *numMatches = 0;		    // return values in case of FAIL
+    *matches = NULL;
 
     // round == 1: Count the matches.
     // round == 2: Build the array to keep the matches.
@@ -1279,6 +1286,7 @@
     {
 	count = 0;
 
+	// First search in map modifier arguments
 	for (i = 0; i < 7; ++i)
 	{
 	    if (i == 0)
@@ -1300,13 +1308,29 @@
 	    else
 		continue;
 
-	    if (vim_regexec(regmatch, p, (colnr_T)0))
+	    if (!fuzzy)
+		match = vim_regexec(regmatch, p, (colnr_T)0);
+	    else
 	    {
-		if (round == 1)
-		    ++count;
-		else
-		    (*file)[count++] = vim_strsave(p);
+		score = fuzzy_match_str(p, pat);
+		match = (score != 0);
 	    }
+
+	    if (!match)
+		continue;
+
+	    if (round == 2)
+	    {
+		if (fuzzy)
+		{
+		    fuzmatch[count].idx = count;
+		    fuzmatch[count].str = vim_strsave(p);
+		    fuzmatch[count].score = score;
+		}
+		else
+		    (*matches)[count] = vim_strsave(p);
+	    }
+	    ++count;
 	}
 
 	for (hash = 0; hash < 256; ++hash)
@@ -1326,14 +1350,31 @@
 		if (mp->m_mode & expand_mapmodes)
 		{
 		    p = translate_mapping(mp->m_keys);
-		    if (p != NULL && vim_regexec(regmatch, p, (colnr_T)0))
+		    if (p != NULL)
 		    {
-			if (round == 1)
-			    ++count;
+			if (!fuzzy)
+			    match = vim_regexec(regmatch, p, (colnr_T)0);
 			else
 			{
-			    (*file)[count++] = p;
-			    p = NULL;
+			    score = fuzzy_match_str(p, pat);
+			    match = (score != 0);
+			}
+
+			if (match)
+			{
+			    if (round == 2)
+			    {
+				if (fuzzy)
+				{
+				    fuzmatch[count].idx = count;
+				    fuzmatch[count].str = p;
+				    fuzmatch[count].score = score;
+				}
+				else
+				    (*matches)[count] = p;
+				p = NULL;
+			    }
+			    ++count;
 			}
 		    }
 		    vim_free(p);
@@ -1346,12 +1387,25 @@
 
 	if (round == 1)
 	{
-	    *file = ALLOC_MULT(char_u *, count);
-	    if (*file == NULL)
-		return FAIL;
+	    if (fuzzy)
+	    {
+		fuzmatch = ALLOC_MULT(fuzmatch_str_T, count);
+		if (fuzmatch == NULL)
+		    return FAIL;
+	    }
+	    else
+	    {
+		*matches = ALLOC_MULT(char_u *, count);
+		if (*matches == NULL)
+		    return FAIL;
+	    }
 	}
     } // for (round)
 
+    if (fuzzy && fuzzymatches_to_strmatches(fuzmatch, matches, count,
+							FALSE) == FAIL)
+	return FAIL;
+
     if (count > 1)
     {
 	char_u	**ptr1;
@@ -1359,10 +1413,12 @@
 	char_u	**ptr3;
 
 	// Sort the matches
-	sort_strings(*file, count);
+	// Fuzzy matching already sorts the matches
+	if (!fuzzy)
+	    sort_strings(*matches, count);
 
 	// Remove multiple entries
-	ptr1 = *file;
+	ptr1 = *matches;
 	ptr2 = ptr1 + 1;
 	ptr3 = ptr1 + count;
 
@@ -1378,7 +1434,7 @@
 	}
     }
 
-    *num_file = count;
+    *numMatches = count;
     return (count == 0 ? FAIL : OK);
 }
 
diff --git a/src/proto/map.pro b/src/proto/map.pro
index 42ebd4b..8b8bc06 100644
--- a/src/proto/map.pro
+++ b/src/proto/map.pro
@@ -8,7 +8,7 @@
 int map_to_exists(char_u *str, char_u *modechars, int abbr);
 int map_to_exists_mode(char_u *rhs, int mode, int abbr);
 char_u *set_context_in_map_cmd(expand_T *xp, char_u *cmd, char_u *arg, int forceit, int isabbrev, int isunmap, cmdidx_T cmdidx);
-int ExpandMappings(regmatch_T *regmatch, int *num_file, char_u ***file);
+int ExpandMappings(char_u *pat, regmatch_T *regmatch, int *num_file, char_u ***file);
 int check_abbr(int c, char_u *ptr, int col, int mincol);
 char_u *eval_map_expr(mapblock_T *mp, int c);
 char_u *vim_strsave_escape_csi(char_u *p);
diff --git a/src/search.c b/src/search.c
index 063058d..98241a4 100644
--- a/src/search.c
+++ b/src/search.c
@@ -5006,7 +5006,7 @@
     if (str == NULL || pat == NULL)
 	return 0;
 
-    fuzzy_match(str, pat, FALSE, &score, matchpos,
+    fuzzy_match(str, pat, TRUE, &score, matchpos,
 				sizeof(matchpos) / sizeof(matchpos[0]));
 
     return score;
diff --git a/src/testdir/test_cmdline.vim b/src/testdir/test_cmdline.vim
index 2fc19c6..d7e46d9 100644
--- a/src/testdir/test_cmdline.vim
+++ b/src/testdir/test_cmdline.vim
@@ -2658,11 +2658,52 @@
   call feedkeys(":mapclear buf\<Tab>\<C-B>\"\<CR>", 'tx')
   call assert_equal('"mapclear <buffer>', @:)
 
-  " map name fuzzy completion - NOT supported
+  " map name fuzzy completion
   " test regex completion works
   set wildoptions=fuzzy
   call feedkeys(":cnoremap <ex\<Tab> <esc> \<Tab>\<C-B>\"\<CR>", 'tx')
   call assert_equal("\"cnoremap <expr> <esc> \<Tab>", @:)
+  nmap <plug>MyLongMap :p<CR>
+  call feedkeys(":nmap MLM\<Tab>\<C-B>\"\<CR>", 'tx')
+  call assert_equal("\"nmap <Plug>MyLongMap", @:)
+  call feedkeys(":nmap MLM \<Tab>\<C-B>\"\<CR>", 'tx')
+  call assert_equal("\"nmap MLM \t", @:)
+  call feedkeys(":nmap <F2> one two \<Tab>\<C-B>\"\<CR>", 'tx')
+  call assert_equal("\"nmap <F2> one two \t", @:)
+  " duplicate entries should be removed
+  vmap <plug>MyLongMap :<C-U>#<CR>
+  call feedkeys(":nmap MLM\<Tab>\<C-B>\"\<CR>", 'tx')
+  call assert_equal("\"nmap <Plug>MyLongMap", @:)
+  nunmap <plug>MyLongMap
+  vunmap <plug>MyLongMap
+  call feedkeys(":nmap ABC\<Tab>\<C-B>\"\<CR>", 'tx')
+  call assert_equal("\"nmap ABC\t", @:)
+  " results should be sorted by best match
+  nmap <Plug>format :
+  nmap <Plug>goformat :
+  nmap <Plug>TestFOrmat :
+  nmap <Plug>fendoff :
+  nmap <Plug>state :
+  nmap <Plug>FendingOff :
+  call feedkeys(":nmap <Plug>fo\<C-A>\<C-B>\"\<CR>", 'tx')
+  call assert_equal("\"nmap <Plug>format <Plug>TestFOrmat <Plug>FendingOff <Plug>goformat <Plug>fendoff", @:)
+  nunmap <Plug>format
+  nunmap <Plug>goformat
+  nunmap <Plug>TestFOrmat
+  nunmap <Plug>fendoff
+  nunmap <Plug>state
+  nunmap <Plug>FendingOff
+
+  " abbreviation fuzzy completion
+  set wildoptions=fuzzy
+  call feedkeys(":iabbr wait\<Tab>\<C-B>\"\<CR>", 'tx')
+  call assert_equal("\"iabbr <nowait>", @:)
+  iabbr WaitForCompletion WFC
+  call feedkeys(":iabbr fcl\<Tab>\<C-B>\"\<CR>", 'tx')
+  call assert_equal("\"iabbr WaitForCompletion", @:)
+  call feedkeys(":iabbr a1z\<Tab>\<C-B>\"\<CR>", 'tx')
+  call assert_equal("\"iabbr a1z\t", @:)
+  iunabbrev WaitForCompletion
 
   " menu name fuzzy completion
   if has('gui_running')
@@ -2792,6 +2833,16 @@
   call assert_equal('"Foo2Bar', @:)
   delcommand Foo2Bar
 
+  " Test for command completion for a command starting with 'k'
+  command KillKillKill :
+  set wildoptions&
+  call feedkeys(":killkill\<Tab>\<C-B>\"\<CR>", 'tx')
+  call assert_equal("\"killkill\<Tab>", @:)
+  set wildoptions=fuzzy
+  call feedkeys(":killkill\<Tab>\<C-B>\"\<CR>", 'tx')
+  call assert_equal('"KillKillKill', @:)
+  delcom KillKillKill
+
   set wildoptions&
   %bw!
 endfunc
diff --git a/src/version.c b/src/version.c
index c77f761..a8c0bdc 100644
--- a/src/version.c
+++ b/src/version.c
@@ -755,6 +755,8 @@
 static int included_patches[] =
 {   /* Add new patch number below this line */
 /**/
+    4479,
+/**/
     4478,
 /**/
     4477,