diff --git a/doc/src/releases.rst b/doc/src/releases.rst
index 7319e53..791ce0c 100644
--- a/doc/src/releases.rst
+++ b/doc/src/releases.rst
@@ -19,6 +19,11 @@ Changed
   are not used anymore.
 - More precise exceptions available in `imapclient.exceptions` are raised when
   an error happens
+- GMail labels are now strings instead of bytes in Python 3.
+
+Fixed
+-----
+- GMail labels using international characters are now handled properly.
 
 Other
 -----
diff --git a/imapclient/imapclient.py b/imapclient/imapclient.py
index bf10a1d..a54f515 100644
--- a/imapclient/imapclient.py
+++ b/imapclient/imapclient.py
@@ -1012,7 +1012,9 @@ class IMAPClient(object):
         attribute (eg. Gmail).
         """
         response = self.fetch(messages, [b'X-GM-LABELS'])
-        return self._filter_fetch_dict(response, b'X-GM-LABELS')
+        response = self._filter_fetch_dict(response, b'X-GM-LABELS')
+        return {msg: utf7_decode_sequence(labels)
+                for msg, labels in iteritems(response)}
 
     def add_gmail_labels(self, messages, labels, silent=False):
         """Add *labels* to *messages* in the currently selected folder.
@@ -1348,8 +1350,10 @@ class IMAPClient(object):
         self._check_resp('OK', command, typ, data)
 
     def _gm_label_store(self, cmd, messages, labels, silent):
-        return self._store(cmd, messages, self._normalise_labels(labels),
+        response = self._store(cmd, messages, self._normalise_labels(labels),
                            b'X-GM-LABELS', silent=silent)
+        return {msg: utf7_decode_sequence(labels)
+                for msg, labels in iteritems(response)} if response else None
 
     def _store(self, cmd, messages, flags, fetch_key, silent):
         """Worker function for the various flag manipulation methods.
@@ -1385,7 +1389,7 @@ class IMAPClient(object):
     def _normalise_labels(self, labels):
         if isinstance(labels, (text_type, binary_type)):
             labels = (labels,)
-        return [_quote(l) for l in labels]
+        return [_quote(encode_utf7(l)) for l in labels]
 
     @property
     def welcome(self):
@@ -1599,6 +1603,10 @@ def debug_trunc(v, maxlen):
     return repr(v[:hl])  + "..." + repr(v[-hl:])
 
 
+def utf7_decode_sequence(seq):
+    return [decode_utf7(s) for s in seq]
+
+
 class IMAPlibLoggerAdapter(LoggerAdapter):
     """Adapter preventing IMAP secrets from going to the logging facility."""
 

UTF-7 decoding of Gmail labels
Originally reported by: **Menno Smits (Bitbucket: [mjs0](https://bitbucket.org/mjs0))**

---

As worked around here in the Nylas sync engine:
https://github.com/nylas/sync-engine/commit/fdeee59be8feea1c4fac4d9972b3462d128c25f2

Fixing this might break backwards compatibility (so might require a 2.0)

---
- Bitbucket: https://bitbucket.org/mjs0/imapclient/issue/184

diff --git a/livetest.py b/livetest.py
index 7e01fa3..1a4a89c 100644
--- a/livetest.py
+++ b/livetest.py
@@ -1,4 +1,5 @@
 #!/usr/bin/python
+# -*- coding: utf-8 -*-
 
 # Copyright (c) 2014, Menno Smits
 # Released subject to the New BSD License
@@ -623,9 +624,9 @@ def createUidTestClass(conf, use_uid):
                 actual_labels = set(answer[msg_id])
                 self.assertSetEqual(actual_labels, set(expected_labels))
 
-            FOO = b'_imapclient_foo'
-            BAR = b'_imapclient_bar'
-            BAZ = b'_imapclient_baz'
+            FOO = '_imapclient_foo'
+            BAR = '_imapclient_bar'
+            BAZ = u'_imapclient_bÂz'
             all_labels = [FOO, BAR, BAZ]
             base_labels = [FOO, BAR]
             try:
diff --git a/tests/test_store.py b/tests/test_store.py
index 8b3319b..2f0911f 100644
--- a/tests/test_store.py
+++ b/tests/test_store.py
@@ -1,3 +1,4 @@
+# -*- coding: utf-8 -*-
 # Copyright (c) 2016, Menno Smits
 # Released subject to the New BSD License
 # Please see http://en.wikipedia.org/wiki/BSD_licenses
@@ -82,12 +83,12 @@ class TestGmailLabels(IMAPClientTest):
 
     def test_get(self):
         with patch.object(self.client, 'fetch', autospec=True,
-                          return_value={123: {b'X-GM-LABELS': [b'foo', b'bar']},
+                          return_value={123: {b'X-GM-LABELS': [b'foo', b'&AUE-abel']},
                                         444: {b'X-GM-LABELS': [b'foo']}}):
             out = self.client.get_gmail_labels(sentinel.messages)
             self.client.fetch.assert_called_with(sentinel.messages, [b'X-GM-LABELS'])
-            self.assertEqual(out, {123: [b'foo', b'bar'],
-                                   444: [b'foo']})
+            self.assertEqual(out, {123: ['foo', u'Łabel'],
+                                   444: ['foo']})
 
     def test_set(self):
         self.check(self.client.set_gmail_labels, b'X-GM-LABELS')
@@ -108,7 +109,7 @@ class TestGmailLabels(IMAPClientTest):
 
         cc = self.client._command_and_check
         cc.return_value = [
-            b'11 (X-GM-LABELS (blah "f\\"o\\"o") UID 1)',
+            b'11 (X-GM-LABELS (&AUE-abel "f\\"o\\"o") UID 1)',
             b'22 (X-GM-LABELS ("f\\"o\\"o") UID 2)',
             b'11 (UID 1 FLAGS (dont))',
             b'22 (UID 2 FLAGS (care))',
@@ -123,8 +124,8 @@ class TestGmailLabels(IMAPClientTest):
             self.assertIsNone(resp)
         else:
             self.assertEqual(resp, {
-                1: (b'blah', b'f"o"o'),
-                2: (b'f"o"o',),
+                1: [u'Łabel', 'f"o"o'],
+                2: ['f"o"o',],
             })
 
         cc.reset_mock()

pip install -e .[dev]
parse_log_pytest
requirements.txt
pytest
apt-get update apt-get install -y gcc
3.6
pytest --no-header -rA --tb=line --color=no -p no:cacheprovider -W ignore::DeprecationWarning
attrs==22.2.0
certifi==2021.5.30
-e git+https://github.com/mjs/imapclient.git@2abdac690fa653fa2d0d55b7617be24101597698#egg=IMAPClient
importlib-metadata==4.8.3
iniconfig==1.1.1
packaging==21.3
pluggy==1.0.0
py==1.11.0
pyparsing==3.1.4
pytest==7.0.1
six==1.17.0
tomli==1.2.3
typing_extensions==4.1.1
zipp==3.6.0

name: imapclient
channels:
  - defaults
  - https://repo.anaconda.com/pkgs/main
  - https://repo.anaconda.com/pkgs/r
  - conda-forge
dependencies:
  - _libgcc_mutex=0.1=main
  - _openmp_mutex=5.1=1_gnu
  - ca-certificates=2025.2.25=h06a4308_0
  - certifi=2021.5.30=py36h06a4308_0
  - ld_impl_linux-64=2.40=h12ee557_0
  - libffi=3.3=he6710b0_2
  - libgcc-ng=11.2.0=h1234567_1
  - libgomp=11.2.0=h1234567_1
  - libstdcxx-ng=11.2.0=h1234567_1
  - ncurses=6.4=h6a678d5_0
  - openssl=1.1.1w=h7f8727e_0
  - pip=21.2.2=py36h06a4308_0
  - python=3.6.13=h12debd9_1
  - readline=8.2=h5eee18b_0
  - setuptools=58.0.4=py36h06a4308_0
  - sqlite=3.45.3=h5eee18b_0
  - tk=8.6.14=h39e8969_0
  - wheel=0.37.1=pyhd3eb1b0_0
  - xz=5.6.4=h5eee18b_1
  - zlib=1.2.13=h5eee18b_1
  - pip:
      - attrs==22.2.0
      - importlib-metadata==4.8.3
      - iniconfig==1.1.1
      - packaging==21.3
      - pluggy==1.0.0
      - py==1.11.0
      - pyparsing==3.1.4
      - pytest==7.0.1
      - six==1.17.0
      - tomli==1.2.3
      - typing-extensions==4.1.1
      - zipp==3.6.0
prefix: /opt/conda/envs/imapclient

tests/test_store.py::TestGmailLabels::test_add tests/test_store.py::TestGmailLabels::test_get tests/test_store.py::TestGmailLabels::test_remove tests/test_store.py::TestGmailLabels::test_set
livetest.py::TestSocketTimeout::test_small_connection_timeout_fail livetest.py::TestSocketTimeout::test_small_read_timeout_fail
tests/test_store.py::TestFlagsConsts::test_flags_are_bytes tests/test_store.py::TestFlags::test_add tests/test_store.py::TestFlags::test_get tests/test_store.py::TestFlags::test_remove tests/test_store.py::TestFlags::test_set
doc/src/releases.rst imapclient/imapclient.py
doc/src/releases.rst imapclient/imapclient.py