diff --git a/Lib/base64.py b/Lib/base64.py
index 4308fb4..c1135a8 100755
--- a/Lib/base64.py
+++ b/Lib/base64.py
@@ -13,7 +13,7 @@
 
 __all__ = [
     # Legacy interface exports traditional RFC 1521 Base64 encodings
-    'encode', 'decode', 'encodestring', 'decodestring',
+    'encode', 'decode', 'encodebytes', 'decodebytes',
     # Generalized interface for other encodings
     'b64encode', 'b64decode', 'b32encode', 'b32decode',
     'b16encode', 'b16decode',
@@ -329,11 +329,9 @@
         output.write(s)
 
 
-def encodestring(s):
-    """Encode a string into multiple lines of base-64 data.
-
-    Argument and return value are bytes.
-    """
+def encodebytes(s):
+    """Encode a bytestring into a bytestring containing multiple lines
+    of base-64 data."""
     if not isinstance(s, bytes_types):
         raise TypeError("expected bytes, not %s" % s.__class__.__name__)
     pieces = []
@@ -342,16 +340,26 @@
         pieces.append(binascii.b2a_base64(chunk))
     return b"".join(pieces)
 
+def encodestring(s):
+    """Legacy alias of encodebytes()."""
+    import warnings
+    warnings.warn("encodestring() is a deprecated alias, use encodebytes()",
+                  DeprecationWarning, 2)
+    return encodebytes(s)
 
-def decodestring(s):
-    """Decode a string.
 
-    Argument and return value are bytes.
-    """
+def decodebytes(s):
+    """Decode a bytestring of base-64 data into a bytestring."""
     if not isinstance(s, bytes_types):
         raise TypeError("expected bytes, not %s" % s.__class__.__name__)
     return binascii.a2b_base64(s)
 
+def decodestring(s):
+    """Legacy alias of decodebytes()."""
+    import warnings
+    warnings.warn("decodestring() is a deprecated alias, use decodebytes()",
+                  DeprecationWarning, 2)
+    return decodebytes(s)
 
 
 # Usable as a script...
diff --git a/Lib/test/test_base64.py b/Lib/test/test_base64.py
index e899016..149ac8a 100644
--- a/Lib/test/test_base64.py
+++ b/Lib/test/test_base64.py
@@ -6,35 +6,35 @@
 
 
 class LegacyBase64TestCase(unittest.TestCase):
-    def test_encodestring(self):
+    def test_encodebytes(self):
         eq = self.assertEqual
-        eq(base64.encodestring(b"www.python.org"), b"d3d3LnB5dGhvbi5vcmc=\n")
-        eq(base64.encodestring(b"a"), b"YQ==\n")
-        eq(base64.encodestring(b"ab"), b"YWI=\n")
-        eq(base64.encodestring(b"abc"), b"YWJj\n")
-        eq(base64.encodestring(b""), b"")
-        eq(base64.encodestring(b"abcdefghijklmnopqrstuvwxyz"
+        eq(base64.encodebytes(b"www.python.org"), b"d3d3LnB5dGhvbi5vcmc=\n")
+        eq(base64.encodebytes(b"a"), b"YQ==\n")
+        eq(base64.encodebytes(b"ab"), b"YWI=\n")
+        eq(base64.encodebytes(b"abc"), b"YWJj\n")
+        eq(base64.encodebytes(b""), b"")
+        eq(base64.encodebytes(b"abcdefghijklmnopqrstuvwxyz"
                                b"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
                                b"0123456789!@#0^&*();:<>,. []{}"),
            b"YWJjZGVmZ2hpamtsbW5vcHFyc3R1dnd4eXpBQkNE"
            b"RUZHSElKS0xNTk9QUVJTVFVWV1hZWjAxMjM0\nNT"
            b"Y3ODkhQCMwXiYqKCk7Ojw+LC4gW117fQ==\n")
-        self.assertRaises(TypeError, base64.encodestring, "")
+        self.assertRaises(TypeError, base64.encodebytes, "")
 
-    def test_decodestring(self):
+    def test_decodebytes(self):
         eq = self.assertEqual
-        eq(base64.decodestring(b"d3d3LnB5dGhvbi5vcmc=\n"), b"www.python.org")
-        eq(base64.decodestring(b"YQ==\n"), b"a")
-        eq(base64.decodestring(b"YWI=\n"), b"ab")
-        eq(base64.decodestring(b"YWJj\n"), b"abc")
-        eq(base64.decodestring(b"YWJjZGVmZ2hpamtsbW5vcHFyc3R1dnd4eXpBQkNE"
+        eq(base64.decodebytes(b"d3d3LnB5dGhvbi5vcmc=\n"), b"www.python.org")
+        eq(base64.decodebytes(b"YQ==\n"), b"a")
+        eq(base64.decodebytes(b"YWI=\n"), b"ab")
+        eq(base64.decodebytes(b"YWJj\n"), b"abc")
+        eq(base64.decodebytes(b"YWJjZGVmZ2hpamtsbW5vcHFyc3R1dnd4eXpBQkNE"
                                b"RUZHSElKS0xNTk9QUVJTVFVWV1hZWjAxMjM0\nNT"
                                b"Y3ODkhQCMwXiYqKCk7Ojw+LC4gW117fQ==\n"),
            b"abcdefghijklmnopqrstuvwxyz"
            b"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
            b"0123456789!@#0^&*();:<>,. []{}")
-        eq(base64.decodestring(b''), b'')
-        self.assertRaises(TypeError, base64.decodestring, "")
+        eq(base64.decodebytes(b''), b'')
+        self.assertRaises(TypeError, base64.decodebytes, "")
 
     def test_encode(self):
         eq = self.assertEqual
diff --git a/Lib/test/test_xmlrpc.py b/Lib/test/test_xmlrpc.py
index 73d53ee..d4e8122 100644
--- a/Lib/test/test_xmlrpc.py
+++ b/Lib/test/test_xmlrpc.py
@@ -232,7 +232,7 @@
 
     def test_decode(self):
         d = b'\x01\x02\x03abc123\xff\xfe'
-        de = base64.encodestring(d)
+        de = base64.encodebytes(d)
         t1 = xmlrpclib.Binary()
         t1.decode(de)
         self.assertEqual(str(t1), str(d, "latin-1"))
diff --git a/Lib/xmlrpc/client.py b/Lib/xmlrpc/client.py
index 05a1c8a..c62dbc4 100644
--- a/Lib/xmlrpc/client.py
+++ b/Lib/xmlrpc/client.py
@@ -419,11 +419,11 @@
         return self.data != other
 
     def decode(self, data):
-        self.data = base64.decodestring(data)
+        self.data = base64.decodebytes(data)
 
     def encode(self, out):
         out.write("<value><base64>\n")
-        encoded = base64.encodestring(self.data)
+        encoded = base64.encodebytes(self.data)
         out.write(encoded.decode('ascii'))
         out.write('\n')
         out.write("</base64></value>\n")
@@ -1100,7 +1100,7 @@
         if auth:
             import base64
             auth = urllib.parse.unquote_to_bytes(auth)
-            auth = base64.encodestring(auth).decode("utf-8")
+            auth = base64.encodebytes(auth).decode("utf-8")
             auth = "".join(auth.split()) # get rid of whitespace
             extra_headers = [
                 ("Authorization", "Basic " + auth)