diff --git a/Doc/library/constants.rst b/Doc/library/constants.rst
index 5017159..f17e1a3 100644
--- a/Doc/library/constants.rst
+++ b/Doc/library/constants.rst
@@ -31,7 +31,7 @@
    etc.) to indicate that the operation is not implemented with respect to
    the other type; may be returned by the in-place binary special methods
    (e.g. :meth:`__imul__`, :meth:`__iand__`, etc.) for the same purpose.
-   Its truth value is true.
+   It should not be evaluated in a boolean context.
 
    .. note::
 
@@ -50,6 +50,11 @@
       even though they have similar names and purposes.
       See :exc:`NotImplementedError` for details on when to use it.
 
+   .. versionchanged:: 3.9
+      Evaluating ``NotImplemented`` in a boolean context is deprecated. While
+      it currently evaluates as true, it will emit a :exc:`DeprecationWarning`.
+      It will raise a :exc:`TypeError` in a future version of Python.
+
 
 .. index:: single: ...; ellipsis literal
 .. data:: Ellipsis
diff --git a/Doc/reference/datamodel.rst b/Doc/reference/datamodel.rst
index 5b3b669..8be432d 100644
--- a/Doc/reference/datamodel.rst
+++ b/Doc/reference/datamodel.rst
@@ -156,13 +156,18 @@
    object is accessed through the built-in name ``NotImplemented``. Numeric methods
    and rich comparison methods should return this value if they do not implement the
    operation for the operands provided.  (The interpreter will then try the
-   reflected operation, or some other fallback, depending on the operator.)  Its
-   truth value is true.
+   reflected operation, or some other fallback, depending on the operator.)  It
+   should not be evaluated in a boolean context.
 
    See
    :ref:`implementing-the-arithmetic-operations`
    for more details.
 
+   .. versionchanged:: 3.9
+      Evaluating ``NotImplemented`` in a boolean context is deprecated. While
+      it currently evaluates as true, it will emit a :exc:`DeprecationWarning`.
+      It will raise a :exc:`TypeError` in a future version of Python.
+
 
 Ellipsis
    .. index::
diff --git a/Doc/whatsnew/3.9.rst b/Doc/whatsnew/3.9.rst
index f49575d..9a8a484 100644
--- a/Doc/whatsnew/3.9.rst
+++ b/Doc/whatsnew/3.9.rst
@@ -452,6 +452,12 @@
   of Python. For the majority of use cases, users can leverage the Abstract Syntax
   Tree (AST) generation and compilation stage, using the :mod:`ast` module.
 
+* Using :data:`NotImplemented` in a boolean context has been deprecated,
+  as it is almost exclusively the result of incorrect rich comparator
+  implementations. It will be made a :exc:`TypeError` in a future version
+  of Python.
+  (Contributed by Josh Rosenberg in :issue:`35712`.)
+
 * The :mod:`random` module currently accepts any hashable type as a
   possible seed value.  Unfortunately, some of those types are not
   guaranteed to have a deterministic hash value.  After Python 3.9,
diff --git a/Lib/functools.py b/Lib/functools.py
index 535fa04..e230175 100644
--- a/Lib/functools.py
+++ b/Lib/functools.py
@@ -96,6 +96,8 @@
 def _le_from_lt(self, other, NotImplemented=NotImplemented):
     'Return a <= b.  Computed by @total_ordering from (a < b) or (a == b).'
     op_result = self.__lt__(other)
+    if op_result is NotImplemented:
+        return op_result
     return op_result or self == other
 
 def _ge_from_lt(self, other, NotImplemented=NotImplemented):
@@ -136,6 +138,8 @@
 def _ge_from_gt(self, other, NotImplemented=NotImplemented):
     'Return a >= b.  Computed by @total_ordering from (a > b) or (a == b).'
     op_result = self.__gt__(other)
+    if op_result is NotImplemented:
+        return op_result
     return op_result or self == other
 
 def _le_from_gt(self, other, NotImplemented=NotImplemented):
diff --git a/Lib/ipaddress.py b/Lib/ipaddress.py
index 9c47405..7024339 100644
--- a/Lib/ipaddress.py
+++ b/Lib/ipaddress.py
@@ -1398,7 +1398,7 @@
 
     def __eq__(self, other):
         address_equal = IPv4Address.__eq__(self, other)
-        if not address_equal or address_equal is NotImplemented:
+        if address_equal is NotImplemented or not address_equal:
             return address_equal
         try:
             return self.network == other.network
@@ -2096,7 +2096,7 @@
 
     def __eq__(self, other):
         address_equal = IPv6Address.__eq__(self, other)
-        if not address_equal or address_equal is NotImplemented:
+        if address_equal is NotImplemented or not address_equal:
             return address_equal
         try:
             return self.network == other.network
@@ -2109,7 +2109,7 @@
     def __lt__(self, other):
         address_less = IPv6Address.__lt__(self, other)
         if address_less is NotImplemented:
-            return NotImplemented
+            return address_less
         try:
             return (self.network < other.network or
                     self.network == other.network and address_less)
diff --git a/Lib/test/test_buffer.py b/Lib/test/test_buffer.py
index 6178ffd..2ddca06 100644
--- a/Lib/test/test_buffer.py
+++ b/Lib/test/test_buffer.py
@@ -2528,7 +2528,7 @@
         values = [INT(9), IDX(9),
                   2.2+3j, Decimal("-21.1"), 12.2, Fraction(5, 2),
                   [1,2,3], {4,5,6}, {7:8}, (), (9,),
-                  True, False, None, NotImplemented,
+                  True, False, None, Ellipsis,
                   b'a', b'abc', bytearray(b'a'), bytearray(b'abc'),
                   'a', 'abc', r'a', r'abc',
                   f, lambda x: x]
diff --git a/Lib/test/test_builtin.py b/Lib/test/test_builtin.py
index 5c553a9..e50c273 100644
--- a/Lib/test/test_builtin.py
+++ b/Lib/test/test_builtin.py
@@ -1666,6 +1666,20 @@
             self.assertRaises(TypeError, tp, 1, 2)
             self.assertRaises(TypeError, tp, a=1, b=2)
 
+    def test_warning_notimplemented(self):
+        # Issue #35712: NotImplemented is a sentinel value that should never
+        # be evaluated in a boolean context (virtually all such use cases
+        # are a result of accidental misuse implementing rich comparison
+        # operations in terms of one another).
+        # For the time being, it will continue to evaluate as truthy, but
+        # issue a deprecation warning (with the eventual intent to make it
+        # a TypeError).
+        self.assertWarns(DeprecationWarning, bool, NotImplemented)
+        with self.assertWarns(DeprecationWarning):
+            self.assertTrue(NotImplemented)
+        with self.assertWarns(DeprecationWarning):
+            self.assertFalse(not NotImplemented)
+
 
 class TestBreakpoint(unittest.TestCase):
     def setUp(self):
diff --git a/Lib/test/test_descr.py b/Lib/test/test_descr.py
index d2e1218..96cc8de2 100644
--- a/Lib/test/test_descr.py
+++ b/Lib/test/test_descr.py
@@ -2526,9 +2526,9 @@
         except TypeError:
             pass
 
-        # Two essentially featureless objects, just inheriting stuff from
-        # object.
-        self.assertEqual(dir(NotImplemented), dir(Ellipsis))
+        # Two essentially featureless objects, (Ellipsis just inherits stuff
+        # from object.
+        self.assertEqual(dir(object()), dir(Ellipsis))
 
         # Nasty test case for proxied objects
         class Wrapper(object):
diff --git a/Misc/NEWS.d/next/Core and Builtins/2019-05-08-11-11-45.bpo-35712.KJthus.rst b/Misc/NEWS.d/next/Core and Builtins/2019-05-08-11-11-45.bpo-35712.KJthus.rst
new file mode 100644
index 0000000..3a68632
--- /dev/null
+++ b/Misc/NEWS.d/next/Core and Builtins/2019-05-08-11-11-45.bpo-35712.KJthus.rst
@@ -0,0 +1,2 @@
+Using :data:`NotImplemented` in a boolean context has been deprecated. Patch
+contributed by Josh Rosenberg.
diff --git a/Objects/object.c b/Objects/object.c
index 81de3b8..9c74e07 100644
--- a/Objects/object.c
+++ b/Objects/object.c
@@ -1673,6 +1673,22 @@
     Py_FatalError("deallocating NotImplemented");
 }
 
+static int
+notimplemented_bool(PyObject *v)
+{
+    if (PyErr_WarnEx(PyExc_DeprecationWarning,
+                     "NotImplemented should not be used in a boolean context",
+                     1) < 0)
+    {
+        return -1;
+    }
+    return 1;
+}
+
+static PyNumberMethods notimplemented_as_number = {
+    .nb_bool = notimplemented_bool,
+};
+
 PyTypeObject _PyNotImplemented_Type = {
     PyVarObject_HEAD_INIT(&PyType_Type, 0)
     "NotImplementedType",
@@ -1683,8 +1699,8 @@
     0,                  /*tp_getattr*/
     0,                  /*tp_setattr*/
     0,                  /*tp_as_async*/
-    NotImplemented_repr, /*tp_repr*/
-    0,                  /*tp_as_number*/
+    NotImplemented_repr,        /*tp_repr*/
+    &notimplemented_as_number,  /*tp_as_number*/
     0,                  /*tp_as_sequence*/
     0,                  /*tp_as_mapping*/
     0,                  /*tp_hash */