diff --git a/src/regexp.c b/src/regexp.c
index 74a73c4..7304bd3 100644
--- a/src/regexp.c
+++ b/src/regexp.c
@@ -1294,6 +1294,34 @@
     return p;
 }
 
+/*
+ * Return TRUE if the back reference is legal. We must have seen the close
+ * brace.
+ * TODO: Should also check that we don't refer to something that is repeated
+ * (+*=): what instance of the repetition should we match?
+ */
+    static int
+seen_endbrace(int refnum)
+{
+    if (!had_endbrace[refnum])
+    {
+	char_u *p;
+
+	/* Trick: check if "@<=" or "@<!" follows, in which case
+	 * the \1 can appear before the referenced match. */
+	for (p = regparse; *p != NUL; ++p)
+	    if (p[0] == '@' && p[1] == '<' && (p[2] == '!' || p[2] == '='))
+		break;
+	if (*p == NUL)
+	{
+	    EMSG(_("E65: Illegal back reference"));
+	    rc_did_emsg = TRUE;
+	    return FALSE;
+	}
+    }
+    return TRUE;
+}
+
 static regprog_T  *bt_regcomp(char_u *expr, int re_flags);
 static void bt_regfree(regprog_T *prog);
 
@@ -2099,24 +2127,8 @@
 		int		    refnum;
 
 		refnum = c - Magic('0');
-		/*
-		 * Check if the back reference is legal. We must have seen the
-		 * close brace.
-		 * TODO: Should also check that we don't refer to something
-		 * that is repeated (+*=): what instance of the repetition
-		 * should we match?
-		 */
-		if (!had_endbrace[refnum])
-		{
-		    /* Trick: check if "@<=" or "@<!" follows, in which case
-		     * the \1 can appear before the referenced match. */
-		    for (p = regparse; *p != NUL; ++p)
-			if (p[0] == '@' && p[1] == '<'
-					      && (p[2] == '!' || p[2] == '='))
-			    break;
-		    if (*p == NUL)
-			EMSG_RET_NULL(_("E65: Illegal back reference"));
-		}
+		if (!seen_endbrace(refnum))
+		    return NULL;
 		ret = regnode(BACKREF + refnum);
 	    }
 	    break;
diff --git a/src/regexp_nfa.c b/src/regexp_nfa.c
index 5ba80f2..804d742 100644
--- a/src/regexp_nfa.c
+++ b/src/regexp_nfa.c
@@ -1446,8 +1446,14 @@
 	case Magic('7'):
 	case Magic('8'):
 	case Magic('9'):
-	    EMIT(NFA_BACKREF1 + (no_Magic(c) - '1'));
-	    nfa_has_backref = TRUE;
+	    {
+		int refnum = no_Magic(c) - '1';
+
+		if (!seen_endbrace(refnum + 1))
+		    return FAIL;
+		EMIT(NFA_BACKREF1 + refnum);
+		nfa_has_backref = TRUE;
+	    }
 	    break;
 
 	case Magic('z'):
diff --git a/src/testdir/test_hlsearch.vim b/src/testdir/test_hlsearch.vim
index b934d38..e9790bb 100644
--- a/src/testdir/test_hlsearch.vim
+++ b/src/testdir/test_hlsearch.vim
@@ -38,11 +38,11 @@
     return
   endif
 
-  " This pattern takes forever to match, it should timeout.
+  " This pattern takes a long time to match, it should timeout.
   help
   let start = reltime()
   set hlsearch nolazyredraw redrawtime=101
-  let @/ = '\%#=2\v(a|\1)*'
+  let @/ = '\%#=1a*.*X\@<=b*'
   redraw
   let elapsed = reltimefloat(reltime(start))
   call assert_true(elapsed > 0.1)
diff --git a/src/testdir/test_regexp_latin.vim b/src/testdir/test_regexp_latin.vim
index 247e5e6..a8fa64d 100644
--- a/src/testdir/test_regexp_latin.vim
+++ b/src/testdir/test_regexp_latin.vim
@@ -62,3 +62,13 @@
     call assert_equal(expected, actual)
   endfor
 endfunc
+
+func Test_backref()
+  new
+  call setline(1, ['one', 'two', 'three', 'four', 'five'])
+  call assert_equal(3, search('\%#=1\(e\)\1'))
+  call assert_equal(3, search('\%#=2\(e\)\1'))
+  call assert_fails('call search("\\%#=1\\(e\\1\\)")', 'E65:')
+  call assert_fails('call search("\\%#=2\\(e\\1\\)")', 'E65:')
+  bwipe!
+endfunc
diff --git a/src/testdir/test_statusline.vim b/src/testdir/test_statusline.vim
index cf85bd5..351b119 100644
--- a/src/testdir/test_statusline.vim
+++ b/src/testdir/test_statusline.vim
@@ -223,7 +223,7 @@
   set statusline=ab%(cd%q%)de
   call assert_match('^abde\s*$', s:get_statusline())
   copen
-  call assert_match('^abcd\[Quickfix List\1]de\s*$', s:get_statusline())
+  call assert_match('^abcd\[Quickfix List]de\s*$', s:get_statusline())
   cclose
 
   " %#: Set highlight group. The name must follow and then a # again.
diff --git a/src/version.c b/src/version.c
index 24bb820..2c3c45a 100644
--- a/src/version.c
+++ b/src/version.c
@@ -765,6 +765,8 @@
 static int included_patches[] =
 {   /* Add new patch number below this line */
 /**/
+    645,
+/**/
     644,
 /**/
     643,