diff --git a/Include/ceval.h b/Include/ceval.h
index 25976bb..10be9d8 100644
--- a/Include/ceval.h
+++ b/Include/ceval.h
@@ -223,7 +223,7 @@
 
 #ifndef Py_LIMITED_API
 PyAPI_FUNC(int) _PyEval_SliceIndex(PyObject *, Py_ssize_t *);
-PyAPI_FUNC(int) _PyEval_SliceIndexOrNone(PyObject *, Py_ssize_t *);
+PyAPI_FUNC(int) _PyEval_SliceIndexNotNone(PyObject *, Py_ssize_t *);
 PyAPI_FUNC(void) _PyEval_SignalAsyncExc(void);
 #endif
 
diff --git a/Misc/NEWS b/Misc/NEWS
index 87b4782..9c434a7 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -10,6 +10,9 @@
 Core and Builtins
 -----------------
 
+- bpo-29935: Fixed error messages in the index() method of tuple, list and deque
+  when pass indices of wrong type.
+
 - bpo-29816: Shift operation now has less opportunity to raise OverflowError.
   ValueError always is raised rather than OverflowError for negative counts.
   Shifting zero with non-negative count always returns zero.
diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c
index b052535..6f78796 100644
--- a/Modules/_collectionsmodule.c
+++ b/Modules/_collectionsmodule.c
@@ -1066,8 +1066,8 @@
         return NULL;
     }
     if (!_PyArg_ParseStack(args, nargs, "O|O&O&:index", &v,
-                           _PyEval_SliceIndex, &start,
-                           _PyEval_SliceIndex, &stop)) {
+                           _PyEval_SliceIndexNotNone, &start,
+                           _PyEval_SliceIndexNotNone, &stop)) {
         return NULL;
     }
 
diff --git a/Objects/clinic/listobject.c.h b/Objects/clinic/listobject.c.h
index eeb932a..43d5599 100644
--- a/Objects/clinic/listobject.c.h
+++ b/Objects/clinic/listobject.c.h
@@ -196,7 +196,7 @@
     Py_ssize_t stop = PY_SSIZE_T_MAX;
 
     if (!_PyArg_ParseStack(args, nargs, "O|O&O&:index",
-        &value, _PyEval_SliceIndex, &start, _PyEval_SliceIndex, &stop)) {
+        &value, _PyEval_SliceIndexNotNone, &start, _PyEval_SliceIndexNotNone, &stop)) {
         goto exit;
     }
 
@@ -297,4 +297,4 @@
 {
     return list___reversed___impl(self);
 }
-/*[clinic end generated code: output=2a3b75efcf858ed5 input=a9049054013a1b77]*/
+/*[clinic end generated code: output=71deae70ca0e6799 input=a9049054013a1b77]*/
diff --git a/Objects/clinic/tupleobject.c.h b/Objects/clinic/tupleobject.c.h
index 12f0df1..880b258 100644
--- a/Objects/clinic/tupleobject.c.h
+++ b/Objects/clinic/tupleobject.c.h
@@ -26,7 +26,7 @@
     Py_ssize_t stop = PY_SSIZE_T_MAX;
 
     if (!_PyArg_ParseStack(args, nargs, "O|O&O&:index",
-        &value, _PyEval_SliceIndex, &start, _PyEval_SliceIndex, &stop)) {
+        &value, _PyEval_SliceIndexNotNone, &start, _PyEval_SliceIndexNotNone, &stop)) {
         goto exit;
     }
 
@@ -99,4 +99,4 @@
 {
     return tuple___getnewargs___impl(self);
 }
-/*[clinic end generated code: output=561a3654411d2225 input=a9049054013a1b77]*/
+/*[clinic end generated code: output=145bcfff64e8c809 input=a9049054013a1b77]*/
diff --git a/Objects/tupleobject.c b/Objects/tupleobject.c
index 9c63983..55da0e3 100644
--- a/Objects/tupleobject.c
+++ b/Objects/tupleobject.c
@@ -534,8 +534,8 @@
 tuple.index
 
     value: object
-    start: object(converter="_PyEval_SliceIndex", type="Py_ssize_t") = 0
-    stop: object(converter="_PyEval_SliceIndex", type="Py_ssize_t", c_default="PY_SSIZE_T_MAX") = sys.maxsize
+    start: slice_index(accept={int}) = 0
+    stop: slice_index(accept={int}, c_default="PY_SSIZE_T_MAX") = sys.maxsize
     /
 
 Return first index of value.
@@ -546,7 +546,7 @@
 static PyObject *
 tuple_index_impl(PyTupleObject *self, PyObject *value, Py_ssize_t start,
                  Py_ssize_t stop)
-/*[clinic end generated code: output=07b6f9f3cb5c33eb input=28890d4bec234471]*/
+/*[clinic end generated code: output=07b6f9f3cb5c33eb input=fb39e9874a21fe3f]*/
 {
     Py_ssize_t i;
 
diff --git a/Python/ceval.c b/Python/ceval.c
index e7ee772..afd305c 100644
--- a/Python/ceval.c
+++ b/Python/ceval.c
@@ -4892,14 +4892,10 @@
    and silently boost values less than -PY_SSIZE_T_MAX-1 to -PY_SSIZE_T_MAX-1.
    Return 0 on error, 1 on success.
 */
-/* Note:  If v is NULL, return success without storing into *pi.  This
-   is because_PyEval_SliceIndex() is called by apply_slice(), which can be
-   called by the SLICE opcode with v and/or w equal to NULL.
-*/
 int
 _PyEval_SliceIndex(PyObject *v, Py_ssize_t *pi)
 {
-    if (v != NULL) {
+    if (v != Py_None) {
         Py_ssize_t x;
         if (PyIndex_Check(v)) {
             x = PyNumber_AsSsize_t(v, NULL);
@@ -4918,9 +4914,22 @@
 }
 
 int
-_PyEval_SliceIndexOrNone(PyObject *v, Py_ssize_t *pi)
+_PyEval_SliceIndexNotNone(PyObject *v, Py_ssize_t *pi)
 {
-    return v == Py_None || _PyEval_SliceIndex(v, pi);
+    Py_ssize_t x;
+    if (PyIndex_Check(v)) {
+        x = PyNumber_AsSsize_t(v, NULL);
+        if (x == -1 && PyErr_Occurred())
+            return 0;
+    }
+    else {
+        PyErr_SetString(PyExc_TypeError,
+                        "slice indices must be integers or "
+                        "have an __index__ method");
+        return 0;
+    }
+    *pi = x;
+    return 1;
 }
 
 
diff --git a/Tools/clinic/clinic.py b/Tools/clinic/clinic.py
index 1d570f1..6be0ab2 100755
--- a/Tools/clinic/clinic.py
+++ b/Tools/clinic/clinic.py
@@ -2670,9 +2670,9 @@
 
     def converter_init(self, *, accept={int, NoneType}):
         if accept == {int}:
-            self.converter = '_PyEval_SliceIndex'
+            self.converter = '_PyEval_SliceIndexNotNone'
         elif accept == {int, NoneType}:
-            self.converter = '_PyEval_SliceIndexOrNone'
+            self.converter = '_PyEval_SliceIndex'
         else:
             fail("slice_index_converter: illegal 'accept' argument " + repr(accept))