diff --git a/src/regexp.c b/src/regexp.c
index d36ac49..bae547c 100644
--- a/src/regexp.c
+++ b/src/regexp.c
@@ -8081,7 +8081,8 @@
      * First try the NFA engine, unless backtracking was requested.
      */
     if (regexp_engine != BACKTRACKING_ENGINE)
-        prog = nfa_regengine.regcomp(expr, re_flags);
+        prog = nfa_regengine.regcomp(expr,
+		re_flags + (regexp_engine == AUTOMATIC_ENGINE ? RE_AUTO : 0));
     else
 	prog = bt_regengine.regcomp(expr, re_flags);
 
@@ -8105,16 +8106,14 @@
 #endif
 	/*
 	 * If the NFA engine failed, try the backtracking engine.
-	 * Disabled for now, both engines fail on the same patterns.
-	 * Re-enable when regcomp() fails when the pattern would work better
-	 * with the other engine.
-	 *
+	 * The NFA engine also fails for patterns that it can't handle well
+	 * but are still valid patterns, thus a retry should work.
+	 */
 	if (regexp_engine == AUTOMATIC_ENGINE)
 	{
+	    regexp_engine = BACKTRACKING_ENGINE;
 	    prog = bt_regengine.regcomp(expr, re_flags);
-	    regexp_engine == BACKTRACKING_ENGINE;
 	}
-	 */
     }
 
     if (prog != NULL)
diff --git a/src/regexp_nfa.c b/src/regexp_nfa.c
index 03d7868..2bd75af 100644
--- a/src/regexp_nfa.c
+++ b/src/regexp_nfa.c
@@ -244,6 +244,9 @@
 static char_u e_misplaced[] = N_("E866: (NFA regexp) Misplaced %c");
 static char_u e_ill_char_class[] = N_("E877: (NFA regexp) Invalid character class: %ld");
 
+/* re_flags passed to nfa_regcomp() */
+static int nfa_re_flags;
+
 /* NFA regexp \ze operator encountered. */
 static int nfa_has_zend;
 
@@ -2011,10 +2014,10 @@
 	     *  <atom>*  */
 	    if (minval == 0 && maxval == MAX_LIMIT)
 	    {
-		if (greedy)
+		if (greedy)		/* { { (match the braces) */
 		    /* \{}, \{0,} */
 		    EMIT(NFA_STAR);
-		else
+		else			/* { { (match the braces) */
 		    /* \{-}, \{-0,} */
 		    EMIT(NFA_STAR_NONGREEDY);
 		break;
@@ -2030,6 +2033,12 @@
 		return OK;
 	    }
 
+	    /* The engine is very inefficient (uses too many states) when the
+	     * maximum is much larger than the minimum.  Bail out if we can
+	     * use the other engine. */
+	    if ((nfa_re_flags & RE_AUTO) && maxval > minval + 200)
+		return FAIL;
+
 	    /* Ignore previous call to nfa_regatom() */
 	    post_ptr = post_start + my_post_start;
 	    /* Save parse state after the repeated atom and the \{} */
@@ -7046,6 +7055,7 @@
 	return NULL;
 
     nfa_regengine.expr = expr;
+    nfa_re_flags = re_flags;
 
     init_class_tab();
 
diff --git a/src/version.c b/src/version.c
index abf41a6..6a40cfa 100644
--- a/src/version.c
+++ b/src/version.c
@@ -742,6 +742,8 @@
 static int included_patches[] =
 {   /* Add new patch number below this line */
 /**/
+    593,
+/**/
     592,
 /**/
     591,
diff --git a/src/vim.h b/src/vim.h
index ea53e00..e359879 100644
--- a/src/vim.h
+++ b/src/vim.h
@@ -1020,6 +1020,7 @@
 #define RE_MAGIC	1	/* 'magic' option */
 #define RE_STRING	2	/* match in string instead of buffer text */
 #define RE_STRICT	4	/* don't allow [abc] without ] */
+#define RE_AUTO		8	/* automatic engine selection */
 
 #ifdef FEAT_SYN_HL
 /* values for reg_do_extmatch */