diff --git a/CHANGELOG.rst b/CHANGELOG.rst
index 48dd0bf..3256031 100644
--- a/CHANGELOG.rst
+++ b/CHANGELOG.rst
@@ -38,6 +38,10 @@
 * Support :class:`~cryptography.hazmat.primitives.hashes.BLAKE2b` and
   :class:`~cryptography.hazmat.primitives.hashes.BLAKE2s` with
   :class:`~cryptography.hazmat.primitives.hmac.HMAC`.
+* Added support for using labels with
+  :class:`~cryptography.hazmat.primitives.asymmetric.padding.OAEP` when using
+  OpenSSL 1.0.2 or greater.
+
 
 
 .. _v2-0-3:
diff --git a/src/cryptography/hazmat/backends/openssl/backend.py b/src/cryptography/hazmat/backends/openssl/backend.py
index 6c9ef84..d9a5bdf 100644
--- a/src/cryptography/hazmat/backends/openssl/backend.py
+++ b/src/cryptography/hazmat/backends/openssl/backend.py
@@ -547,7 +547,11 @@
         elif isinstance(padding, OAEP) and isinstance(padding._mgf, MGF1):
             return (
                 self._oaep_hash_supported(padding._mgf._algorithm) and
-                self._oaep_hash_supported(padding._algorithm)
+                self._oaep_hash_supported(padding._algorithm) and
+                (
+                    (padding._label is None or len(padding._label) == 0) or
+                    self._lib.Cryptography_HAS_RSA_OAEP_LABEL == 1
+                )
             )
         else:
             return False
diff --git a/src/cryptography/hazmat/backends/openssl/rsa.py b/src/cryptography/hazmat/backends/openssl/rsa.py
index 839ef14..05b4e9d 100644
--- a/src/cryptography/hazmat/backends/openssl/rsa.py
+++ b/src/cryptography/hazmat/backends/openssl/rsa.py
@@ -57,9 +57,6 @@
                 _Reasons.UNSUPPORTED_PADDING
             )
 
-        if padding._label is not None and padding._label != b"":
-            raise ValueError("This backend does not support OAEP labels.")
-
     else:
         raise UnsupportedAlgorithm(
             "{0} is not supported by this backend.".format(
@@ -106,6 +103,21 @@
         res = backend._lib.EVP_PKEY_CTX_set_rsa_oaep_md(pkey_ctx, oaep_md)
         backend.openssl_assert(res > 0)
 
+    if (
+        isinstance(padding, OAEP) and
+        padding._label is not None and
+        len(padding._label) > 0
+    ):
+        # set0_rsa_oaep_label takes ownership of the char * so we need to
+        # copy it into some new memory
+        labelptr = backend._lib.OPENSSL_malloc(len(padding._label))
+        backend.openssl_assert(labelptr != backend._ffi.NULL)
+        backend._ffi.memmove(labelptr, padding._label, len(padding._label))
+        res = backend._lib.EVP_PKEY_CTX_set0_rsa_oaep_label(
+            pkey_ctx, labelptr, len(padding._label)
+        )
+        backend.openssl_assert(res == 1)
+
     outlen = backend._ffi.new("size_t *", buf_size)
     buf = backend._ffi.new("unsigned char[]", buf_size)
     res = crypt(pkey_ctx, buf, outlen, data, len(data))
diff --git a/tests/hazmat/backends/test_openssl.py b/tests/hazmat/backends/test_openssl.py
index 3a847cd..40e9285 100644
--- a/tests/hazmat/backends/test_openssl.py
+++ b/tests/hazmat/backends/test_openssl.py
@@ -422,18 +422,6 @@
                 )
             )
 
-    def test_unsupported_oaep_label_decrypt(self):
-        private_key = RSA_KEY_512.private_key(backend)
-        with pytest.raises(ValueError):
-            private_key.decrypt(
-                b"0" * 64,
-                padding.OAEP(
-                    mgf=padding.MGF1(algorithm=hashes.SHA1()),
-                    algorithm=hashes.SHA1(),
-                    label=b"label"
-                )
-            )
-
 
 class TestOpenSSLCMAC(object):
     def test_unsupported_cipher(self):
diff --git a/tests/hazmat/primitives/test_rsa.py b/tests/hazmat/primitives/test_rsa.py
index 627248f..fc956ec 100644
--- a/tests/hazmat/primitives/test_rsa.py
+++ b/tests/hazmat/primitives/test_rsa.py
@@ -38,8 +38,8 @@
     DummyAsymmetricPadding, DummyHashAlgorithm, DummyKeySerializationEncryption
 )
 from ...utils import (
-    load_pkcs1_vectors, load_rsa_nist_vectors, load_vectors_from_file,
-    raises_unsupported_algorithm
+    load_nist_vectors, load_pkcs1_vectors, load_rsa_nist_vectors,
+    load_vectors_from_file, raises_unsupported_algorithm
 )
 
 
@@ -218,6 +218,133 @@
         assert public_num.n == public_num2.n
         assert public_num.e == public_num2.e
 
+    @pytest.mark.parametrize(
+        "vector",
+        load_vectors_from_file(
+            os.path.join("asymmetric", "RSA", "oaep-label.txt"),
+            load_nist_vectors)
+    )
+    @pytest.mark.supported(
+        only_if=lambda backend: backend.rsa_padding_supported(
+            padding.OAEP(
+                mgf=padding.MGF1(algorithm=hashes.SHA256()),
+                algorithm=hashes.SHA256(),
+                label=b"label"
+            )
+        ),
+        skip_message="Does not support RSA OAEP labels"
+    )
+    def test_oaep_label_decrypt(self, vector, backend):
+        private_key = serialization.load_der_private_key(
+            binascii.unhexlify(vector["key"]), None, backend
+        )
+        assert vector["oaepdigest"] == b"SHA512"
+        decrypted = private_key.decrypt(
+            binascii.unhexlify(vector["input"]),
+            padding.OAEP(
+                mgf=padding.MGF1(algorithm=hashes.SHA512()),
+                algorithm=hashes.SHA512(),
+                label=binascii.unhexlify(vector["oaeplabel"])
+            )
+        )
+        assert vector["output"][1:-1] == decrypted
+
+    @pytest.mark.parametrize(
+        ("msg", "label"),
+        [
+            (b"amazing encrypted msg", b"some label"),
+            (b"amazing encrypted msg", b""),
+        ]
+    )
+    @pytest.mark.supported(
+        only_if=lambda backend: backend.rsa_padding_supported(
+            padding.OAEP(
+                mgf=padding.MGF1(algorithm=hashes.SHA256()),
+                algorithm=hashes.SHA256(),
+                label=b"label"
+            )
+        ),
+        skip_message="Does not support RSA OAEP labels"
+    )
+    def test_oaep_label_roundtrip(self, msg, label, backend):
+        private_key = RSA_KEY_2048.private_key(backend)
+        ct = private_key.public_key().encrypt(
+            msg,
+            padding.OAEP(
+                mgf=padding.MGF1(algorithm=hashes.SHA256()),
+                algorithm=hashes.SHA256(),
+                label=label
+            )
+        )
+        pt = private_key.decrypt(
+            ct,
+            padding.OAEP(
+                mgf=padding.MGF1(algorithm=hashes.SHA256()),
+                algorithm=hashes.SHA256(),
+                label=label
+            )
+        )
+        assert pt == msg
+
+    @pytest.mark.parametrize(
+        ("enclabel", "declabel"),
+        [
+            (b"label1", b"label2"),
+            (b"label3", b""),
+            (b"", b"label4"),
+        ]
+    )
+    @pytest.mark.supported(
+        only_if=lambda backend: backend.rsa_padding_supported(
+            padding.OAEP(
+                mgf=padding.MGF1(algorithm=hashes.SHA256()),
+                algorithm=hashes.SHA256(),
+                label=b"label"
+            )
+        ),
+        skip_message="Does not support RSA OAEP labels"
+    )
+    def test_oaep_wrong_label(self, enclabel, declabel, backend):
+        private_key = RSA_KEY_2048.private_key(backend)
+        msg = b"test"
+        ct = private_key.public_key().encrypt(
+            msg, padding.OAEP(
+                mgf=padding.MGF1(algorithm=hashes.SHA256()),
+                algorithm=hashes.SHA256(),
+                label=enclabel
+            )
+        )
+        with pytest.raises(ValueError):
+            private_key.decrypt(
+                ct, padding.OAEP(
+                    mgf=padding.MGF1(algorithm=hashes.SHA256()),
+                    algorithm=hashes.SHA256(),
+                    label=declabel
+                )
+            )
+
+    @pytest.mark.supported(
+        only_if=lambda backend: not backend.rsa_padding_supported(
+            padding.OAEP(
+                mgf=padding.MGF1(algorithm=hashes.SHA256()),
+                algorithm=hashes.SHA256(),
+                label=b"label"
+            )
+        ),
+        skip_message="Requires backend without RSA OAEP label support"
+    )
+    def test_unsupported_oaep_label_decrypt(self, backend):
+        private_key = RSA_KEY_512.private_key(backend)
+        with raises_unsupported_algorithm(_Reasons.UNSUPPORTED_PADDING):
+            private_key.decrypt(
+                b"0" * 64,
+                padding.OAEP(
+                    mgf=padding.MGF1(algorithm=hashes.SHA1()),
+                    algorithm=hashes.SHA1(),
+                    label=b"label"
+                )
+            )
+
 
 def test_rsa_generate_invalid_backend():
     pretend_backend = object()