diff --git a/Doc/library/base64.rst b/Doc/library/base64.rst
index 080d9d7..ceecf17 100644
--- a/Doc/library/base64.rst
+++ b/Doc/library/base64.rst
@@ -237,14 +237,18 @@
 
 
 .. function:: decodebytes(s)
-              decodestring(s)
 
    Decode the :term:`bytes-like object` *s*, which must contain one or more
    lines of base64 encoded data, and return the decoded :class:`bytes`.
-   ``decodestring`` is a deprecated alias.
 
    .. versionadded:: 3.1
 
+.. function:: decodestring(s)
+
+   Deprecated alias of :func:`decodebytes`.
+
+   .. deprecated:: 3.1
+
 
 .. function:: encode(input, output)
 
@@ -257,14 +261,19 @@
 
 
 .. function:: encodebytes(s)
-              encodestring(s)
 
    Encode the :term:`bytes-like object` *s*, which can contain arbitrary binary
    data, and return :class:`bytes` containing the base64-encoded data, with newlines
    (``b'\n'``) inserted after every 76 bytes of output, and ensuring that
    there is a trailing newline, as per :rfc:`2045` (MIME).
 
-   ``encodestring`` is a deprecated alias.
+   .. versionadded:: 3.1
+
+.. function:: encodestring(s)
+
+   Deprecated alias of :func:`encodebytes`.
+
+   .. deprecated:: 3.1
 
 
 An example usage of the module:
diff --git a/Lib/base64.py b/Lib/base64.py
index 58f6ad6..eb8f258 100755
--- a/Lib/base64.py
+++ b/Lib/base64.py
@@ -541,7 +541,8 @@
 def encodestring(s):
     """Legacy alias of encodebytes()."""
     import warnings
-    warnings.warn("encodestring() is a deprecated alias, use encodebytes()",
+    warnings.warn("encodestring() is a deprecated alias since 3.1, "
+                  "use encodebytes()",
                   DeprecationWarning, 2)
     return encodebytes(s)
 
@@ -554,7 +555,8 @@
 def decodestring(s):
     """Legacy alias of decodebytes()."""
     import warnings
-    warnings.warn("decodestring() is a deprecated alias, use decodebytes()",
+    warnings.warn("decodestring() is a deprecated alias since Python 3.1, "
+                  "use decodebytes()",
                   DeprecationWarning, 2)
     return decodebytes(s)
 
diff --git a/Lib/test/test_base64.py b/Lib/test/test_base64.py
index 4f86aaa..4754739 100644
--- a/Lib/test/test_base64.py
+++ b/Lib/test/test_base64.py
@@ -18,6 +18,14 @@
         int_data = memoryview(b"1234").cast('I')
         self.assertRaises(TypeError, f, int_data)
 
+    def test_encodestring_warns(self):
+        with self.assertWarns(DeprecationWarning):
+            base64.encodestring(b"www.python.org")
+
+    def test_decodestring_warns(self):
+        with self.assertWarns(DeprecationWarning):
+            base64.decodestring(b"d3d3LnB5dGhvbi5vcmc=\n")
+
     def test_encodebytes(self):
         eq = self.assertEqual
         eq(base64.encodebytes(b"www.python.org"), b"d3d3LnB5dGhvbi5vcmc=\n")