diff --git a/Include/ceval.h b/Include/ceval.h
index c5ccf47..70306b8 100644
--- a/Include/ceval.h
+++ b/Include/ceval.h
@@ -93,21 +93,19 @@
       PyThreadState_GET()->overflowed = 0;  \
     } while(0)
 PyAPI_FUNC(int) _Py_CheckRecursiveCall(const char *where);
-/* XXX _Py_CheckRecursionLimit should be changed to
-   _PyRuntime.ceval.check_recursion_limit.  However, due to the macros
-   in which it's used, _Py_CheckRecursionLimit is stuck in the stable
-   ABI.  It should be removed therefrom when possible.
+
+/* Due to the macros in which it's used, _Py_CheckRecursionLimit is in
+   the stable ABI.  It should be removed therefrom when possible.
 */
 PyAPI_DATA(int) _Py_CheckRecursionLimit;
 
 #ifdef USE_STACKCHECK
-/* With USE_STACKCHECK, we artificially decrement the recursion limit in order
-   to trigger regular stack checks in _Py_CheckRecursiveCall(), except if
-   the "overflowed" flag is set, in which case we need the true value
-   of _Py_CheckRecursionLimit for _Py_MakeEndRecCheck() to function properly.
+/* With USE_STACKCHECK, trigger stack checks in _Py_CheckRecursiveCall()
+   on every 64th call to Py_EnterRecursiveCall.
 */
 #  define _Py_MakeRecCheck(x)  \
-    (++(x) > (_Py_CheckRecursionLimit += PyThreadState_GET()->overflowed - 1))
+    (++(x) > _Py_CheckRecursionLimit || \
+     ++(PyThreadState_GET()->stackcheck_counter) > 64)
 #else
 #  define _Py_MakeRecCheck(x)  (++(x) > _Py_CheckRecursionLimit)
 #endif
diff --git a/Include/internal/ceval.h b/Include/internal/ceval.h
index 57db9b1..cdabb95 100644
--- a/Include/internal/ceval.h
+++ b/Include/internal/ceval.h
@@ -29,7 +29,6 @@
 
 struct _ceval_runtime_state {
     int recursion_limit;
-    int check_recursion_limit;
     /* Records whether tracing is on for any thread.  Counts the number
        of threads for which tstate->c_tracefunc is non-NULL, so if the
        value is 0, we know we don't have to check this thread's
diff --git a/Include/pystate.h b/Include/pystate.h
index 238008f..0821238 100644
--- a/Include/pystate.h
+++ b/Include/pystate.h
@@ -151,6 +151,8 @@
                         to handle the runtime error. */
     char recursion_critical; /* The current calls must not cause
                                 a stack overflow. */
+    int stackcheck_counter;
+
     /* 'tracing' keeps track of the execution depth when tracing/profiling.
        This is to prevent the actual trace/profile code from being recorded in
        the trace/profile. */
diff --git a/Misc/NEWS.d/next/Windows/2017-10-23-18-35-50.bpo-31857.YwhEvc.rst b/Misc/NEWS.d/next/Windows/2017-10-23-18-35-50.bpo-31857.YwhEvc.rst
new file mode 100644
index 0000000..13a4978
--- /dev/null
+++ b/Misc/NEWS.d/next/Windows/2017-10-23-18-35-50.bpo-31857.YwhEvc.rst
@@ -0,0 +1,2 @@
+Make the behavior of USE_STACKCHECK deterministic in a multi-threaded
+environment.
diff --git a/Python/ceval.c b/Python/ceval.c
index 58a2513..f6519cf 100644
--- a/Python/ceval.c
+++ b/Python/ceval.c
@@ -469,13 +469,15 @@
     int recursion_limit = _PyRuntime.ceval.recursion_limit;
 
 #ifdef USE_STACKCHECK
+    tstate->stackcheck_counter = 0;
     if (PyOS_CheckStack()) {
         --tstate->recursion_depth;
         PyErr_SetString(PyExc_MemoryError, "Stack overflow");
         return -1;
     }
-#endif
+    /* Needed for ABI backwards-compatibility (see bpo-31857) */
     _Py_CheckRecursionLimit = recursion_limit;
+#endif
     if (tstate->recursion_critical)
         /* Somebody asked that we don't check for recursion. */
         return 0;
diff --git a/Python/pystate.c b/Python/pystate.c
index d85d604..82ebf4d 100644
--- a/Python/pystate.c
+++ b/Python/pystate.c
@@ -245,6 +245,7 @@
         tstate->recursion_depth = 0;
         tstate->overflowed = 0;
         tstate->recursion_critical = 0;
+        tstate->stackcheck_counter = 0;
         tstate->tracing = 0;
         tstate->use_tracing = 0;
         tstate->gilstate_counter = 0;