diff --git a/cryptography/hazmat/backends/openssl/backend.py b/cryptography/hazmat/backends/openssl/backend.py
index a68bc08..7358280 100644
--- a/cryptography/hazmat/backends/openssl/backend.py
+++ b/cryptography/hazmat/backends/openssl/backend.py
@@ -27,6 +27,9 @@
 from cryptography.hazmat.bindings.openssl.binding import Binding
 from cryptography.hazmat.primitives import interfaces, hashes
 from cryptography.hazmat.primitives.asymmetric import rsa
+from cryptography.hazmat.primitives.asymmetric.padding import (
+    PKCS1v15, PSS, MGF1
+)
 from cryptography.hazmat.primitives.ciphers.algorithms import (
     AES, Blowfish, Camellia, CAST5, TripleDES, ARC4, IDEA
 )
@@ -377,6 +380,12 @@
         return _RSAVerificationContext(self, public_key, signature, padding,
                                        algorithm)
 
+    def mgf1_hash_supported(self, algorithm):
+        if self._lib.Cryptography_HAS_MGF1_MD:
+            return self.hash_supported(algorithm)
+        else:
+            return isinstance(algorithm, hashes.SHA1)
+
 
 class GetCipherByName(object):
     def __init__(self, fmt):
@@ -760,12 +769,26 @@
             raise TypeError(
                 "Expected provider of interfaces.AsymmetricPadding")
 
-        if padding.name == "EMSA-PKCS1-v1_5":
+        if isinstance(padding, PKCS1v15):
             if self._backend._lib.Cryptography_HAS_PKEY_CTX:
                 self._verify_method = self._verify_pkey_ctx
                 self._padding_enum = self._backend._lib.RSA_PKCS1_PADDING
             else:
                 self._verify_method = self._verify_pkcs1
+        elif isinstance(padding, PSS):
+            if not isinstance(padding.mgf, MGF1):
+                raise TypeError("Only MGF1 is supported by this backend")
+
+            if (not isinstance(padding.mgf._algorithm, hashes.SHA1) and
+                    not self._backend._lib.Cryptography_HAS_MGF1_MD):
+                raise UnsupportedHash("This backend only supports MGF1 with "
+                                      "SHA1 when OpenSSL is not 1.0.1+")
+
+            if self._backend._lib.Cryptography_HAS_PKEY_CTX:
+                self._verify_method = self._verify_pkey_ctx
+                self._padding_enum = self._backend._lib.RSA_PKCS1_PSS_PADDING
+            else:
+                self._verify_method = self._verify_pss
         else:
             raise UnsupportedPadding
 
@@ -806,6 +829,20 @@
         res = self._backend._lib.EVP_PKEY_CTX_set_rsa_padding(
             pkey_ctx, self._padding_enum)
         assert res > 0
+        if isinstance(self._padding, PSS):
+            res = self._backend._lib.EVP_PKEY_CTX_set_rsa_pss_saltlen(
+                pkey_ctx, self._get_salt_length())
+            assert res > 0
+            if self._backend._lib.Cryptography_HAS_MGF1_MD:
+                # MGF1 MD is configurable in OpenSSL 1.0.1+
+                mgf1_md = self._backend._lib.EVP_get_digestbyname(
+                    self._padding.mgf._algorithm.name.encode("ascii"))
+                assert mgf1_md != self._backend._ffi.NULL
+                res = self._backend._lib.EVP_PKEY_CTX_set_rsa_mgf1_md(
+                    pkey_ctx, mgf1_md
+                )
+                assert res > 0
+
         data_to_verify = self._hash_ctx.finalize()
         self._hash_ctx = None
         res = self._backend._lib.EVP_PKEY_verify(
@@ -842,5 +879,39 @@
             assert errors
             raise InvalidSignature
 
+    def _verify_pss(self, rsa_cdata, evp_pkey, evp_md):
+        pkey_size = self._backend._lib.EVP_PKEY_size(evp_pkey)
+        assert pkey_size > 0
+        buf = self._backend._ffi.new("unsigned char[]", pkey_size)
+        res = self._backend._lib.RSA_public_decrypt(
+            len(self._signature),
+            self._signature,
+            buf,
+            rsa_cdata,
+            self._backend._lib.RSA_NO_PADDING
+        )
+        if res != pkey_size:
+            assert self._backend._consume_errors()
+            raise InvalidSignature
+
+        data_to_verify = self._hash_ctx.finalize()
+        self._hash_ctx = None
+        res = self._backend._lib.RSA_verify_PKCS1_PSS(
+            rsa_cdata,
+            data_to_verify,
+            evp_md,
+            buf,
+            self._get_salt_length()
+        )
+        if res != 1:
+            assert self._backend._consume_errors()
+            raise InvalidSignature
+
+    def _get_salt_length(self):
+        if self._padding.mgf._salt_length is MGF1.MAX_LENGTH:
+            return -2
+        else:
+            return self._padding.mgf._salt_length
+
 
 backend = Backend()
diff --git a/cryptography/hazmat/primitives/asymmetric/padding.py b/cryptography/hazmat/primitives/asymmetric/padding.py
index 46e00b8..a812980 100644
--- a/cryptography/hazmat/primitives/asymmetric/padding.py
+++ b/cryptography/hazmat/primitives/asymmetric/padding.py
@@ -24,6 +24,14 @@
     name = "EMSA-PKCS1-v1_5"
 
 
+@utils.register_interface(interfaces.AsymmetricPadding)
+class PSS(object):
+    name = "EMSA-PSS"
+
+    def __init__(self, mgf):
+        self.mgf = mgf
+
+
 class MGF1(object):
     MAX_LENGTH = object()
 
diff --git a/docs/hazmat/primitives/asymmetric/padding.rst b/docs/hazmat/primitives/asymmetric/padding.rst
index 8a03432..aa48b31 100644
--- a/docs/hazmat/primitives/asymmetric/padding.rst
+++ b/docs/hazmat/primitives/asymmetric/padding.rst
@@ -17,6 +17,18 @@
     PKCS1 v1.5 (also known as simply PKCS1) is a simple padding scheme
     developed for use with RSA keys. It is defined in :rfc:`3447`.
 
+.. class:: PSS(mgf)
+
+    .. versionadded:: 0.3
+
+    PSS (Probabilistic Signature Scheme) is a signature scheme defined in
+    :rfc:`3447`. It is more complex than PKCS1 but possesses a `security proof`_.
+    This is the recommended padding algorithm for RSA.
+
+    :param mgf: A mask generation function object. At this time the only
+        supported MGF is :class:`MGF1`.
+
+
 Mask Generation Functions
 ~~~~~~~~~~~~~~~~~~~~~~~~~
 
@@ -41,3 +53,4 @@
 
 
 .. _`Padding is critical`: http://rdist.root.org/2009/10/06/why-rsa-encryption-padding-is-critical/
+.. _`security proof`: http://eprint.iacr.org/2001/062.pdf
diff --git a/tests/hazmat/primitives/test_rsa.py b/tests/hazmat/primitives/test_rsa.py
index 0e88bb7..8e9637f 100644
--- a/tests/hazmat/primitives/test_rsa.py
+++ b/tests/hazmat/primitives/test_rsa.py
@@ -25,7 +25,10 @@
 from cryptography.hazmat.primitives import hashes, interfaces
 from cryptography.hazmat.primitives.asymmetric import rsa, padding
 
-from ...utils import load_pkcs1_vectors, load_vectors_from_file
+from .utils import generate_rsa_pss_test
+from ...utils import (
+    load_pkcs1_vectors, load_vectors_from_file, load_rsa_nist_vectors
+)
 
 
 @utils.register_interface(interfaces.AsymmetricPadding)
@@ -33,6 +36,10 @@
     name = "UNSUPPORTED-PADDING"
 
 
+class DummyMGF(object):
+    pass
+
+
 def _modinv(e, m):
     """
     Modular Multiplicative Inverse.  Returns x such that: (x*e) mod m == 1
@@ -530,6 +537,122 @@
         with pytest.raises(exceptions.InvalidSignature):
             verifier.verify()
 
+    @pytest.mark.parametrize(
+        "pkcs1_example",
+        _flatten_pkcs1_examples(load_vectors_from_file(
+            os.path.join(
+                "asymmetric", "RSA", "pkcs-1v2-1d2-vec", "pss-vect.txt"),
+            load_pkcs1_vectors
+        ))
+    )
+    def test_pss_verification(self, pkcs1_example, backend):
+        private, public, example = pkcs1_example
+        public_key = rsa.RSAPublicKey(
+            public_exponent=public["public_exponent"],
+            modulus=public["modulus"]
+        )
+        verifier = public_key.verifier(
+            binascii.unhexlify(example["signature"]),
+            padding.PSS(
+                mgf=padding.MGF1(
+                    algorithm=hashes.SHA1(),
+                    salt_length=padding.MGF1.MAX_LENGTH
+                )
+            ),
+            hashes.SHA1(),
+            backend
+        )
+        verifier.update(binascii.unhexlify(example["message"]))
+        verifier.verify()
+
+    def test_invalid_pss_signature_wrong_data(self, backend):
+        public_key = rsa.RSAPublicKey(
+            modulus=int(
+                b"dffc2137d5e810cde9e4b4612f5796447218bab913b3fa98bdf7982e4fa6"
+                b"ec4d6653ef2b29fb1642b095befcbea6decc178fb4bed243d3c3592c6854"
+                b"6af2d3f3", 16
+            ),
+            public_exponent=65537
+        )
+        signature = binascii.unhexlify(
+            b"0e68c3649df91c5bc3665f96e157efa75b71934aaa514d91e94ca8418d100f45"
+            b"6f05288e58525f99666bab052adcffdf7186eb40f583bd38d98c97d3d524808b"
+        )
+        verifier = public_key.verifier(
+            signature,
+            padding.PSS(
+                mgf=padding.MGF1(
+                    algorithm=hashes.SHA1(),
+                    salt_length=padding.MGF1.MAX_LENGTH
+                )
+            ),
+            hashes.SHA1(),
+            backend
+        )
+        verifier.update(b"incorrect data")
+        with pytest.raises(exceptions.InvalidSignature):
+            verifier.verify()
+
+    def test_invalid_pss_signature_wrong_key(self, backend):
+        signature = binascii.unhexlify(
+            b"3a1880165014ba6eb53cc1449d13e5132ebcc0cfd9ade6d7a2494a0503bd0826"
+            b"f8a46c431e0d7be0ca3e453f8b2b009e2733764da7927cc6dbe7a021437a242e"
+        )
+        public_key = rsa.RSAPublicKey(
+            modulus=int(
+                b"381201f4905d67dfeb3dec131a0fbea773489227ec7a1448c3109189ac68"
+                b"5a95441be90866a14c4d2e139cd16db540ec6c7abab13ffff91443fd46a8"
+                b"960cbb7658ded26a5c95c86f6e40384e1c1239c63e541ba221191c4dd303"
+                b"231b42e33c6dbddf5ec9a746f09bf0c25d0f8d27f93ee0ae5c0d723348f4"
+                b"030d3581e13522e1", 16
+            ),
+            public_exponent=65537
+        )
+        verifier = public_key.verifier(
+            signature,
+            padding.PSS(
+                mgf=padding.MGF1(
+                    algorithm=hashes.SHA1(),
+                    salt_length=padding.MGF1.MAX_LENGTH
+                )
+            ),
+            hashes.SHA1(),
+            backend
+        )
+        verifier.update(b"sign me")
+        with pytest.raises(exceptions.InvalidSignature):
+            verifier.verify()
+
+    def test_invalid_pss_signature_data_too_large_for_modulus(self, backend):
+        signature = binascii.unhexlify(
+            b"cb43bde4f7ab89eb4a79c6e8dd67e0d1af60715da64429d90c716a490b799c29"
+            b"194cf8046509c6ed851052367a74e2e92d9b38947ed74332acb115a03fcc0222"
+        )
+        public_key = rsa.RSAPublicKey(
+            modulus=int(
+                b"381201f4905d67dfeb3dec131a0fbea773489227ec7a1448c3109189ac68"
+                b"5a95441be90866a14c4d2e139cd16db540ec6c7abab13ffff91443fd46a8"
+                b"960cbb7658ded26a5c95c86f6e40384e1c1239c63e541ba221191c4dd303"
+                b"231b42e33c6dbddf5ec9a746f09bf0c25d0f8d27f93ee0ae5c0d723348f4"
+                b"030d3581e13522", 16
+            ),
+            public_exponent=65537
+        )
+        verifier = public_key.verifier(
+            signature,
+            padding.PSS(
+                mgf=padding.MGF1(
+                    algorithm=hashes.SHA1(),
+                    salt_length=padding.MGF1.MAX_LENGTH
+                )
+            ),
+            hashes.SHA1(),
+            backend
+        )
+        verifier.update(b"sign me")
+        with pytest.raises(exceptions.InvalidSignature):
+            verifier.verify()
+
     def test_use_after_finalize(self, backend):
         private_key = rsa.RSAPrivateKey.generate(
             public_exponent=65537,
@@ -583,6 +706,130 @@
             public_key.verifier(
                 b"foo", padding.PKCS1v15(), hashes.SHA256(), pretend_backend)
 
+    def test_unsupported_pss_mgf(self, backend):
+        private_key = rsa.RSAPrivateKey.generate(
+            public_exponent=65537,
+            key_size=512,
+            backend=backend
+        )
+        public_key = private_key.public_key()
+        with pytest.raises(TypeError):
+            public_key.verifier(b"sig", padding.PSS(mgf=DummyMGF()),
+                                hashes.SHA1(), backend)
+
+    def test_pss_verify_salt_length_too_long(self, backend):
+        signature = binascii.unhexlify(
+            b"8b9a3ae9fb3b64158f3476dd8d8a1f1425444e98940e0926378baa9944d219d8"
+            b"534c050ef6b19b1bdc6eb4da422e89161106a6f5b5cc16135b11eb6439b646bd"
+        )
+        public_key = rsa.RSAPublicKey(
+            modulus=int(
+                b"d309e4612809437548b747d7f9eb9cd3340f54fe42bb3f84a36933b0839c"
+                b"11b0c8b7f67e11f7252370161e31159c49c784d4bc41c42a78ce0f0b40a3"
+                b"ca8ffb91", 16
+            ),
+            public_exponent=65537
+        )
+        verifier = public_key.verifier(
+            signature,
+            padding.PSS(
+                mgf=padding.MGF1(
+                    algorithm=hashes.SHA1(),
+                    salt_length=1000000
+                )
+            ),
+            hashes.SHA1(),
+            backend
+        )
+        verifier.update(b"sign me")
+        with pytest.raises(exceptions.InvalidSignature):
+            verifier.verify()
+
+
+@pytest.mark.supported(
+    only_if=lambda backend: backend.mgf1_hash_supported(hashes.SHA1()),
+    skip_message="Does not support SHA1 with MGF1."
+)
+@pytest.mark.rsa
+class TestRSAPSSMGF1VerificationSHA1(object):
+    test_rsa_pss_mgf1_sha1 = generate_rsa_pss_test(
+        load_rsa_nist_vectors,
+        os.path.join("asymmetric", "RSA", "FIPS_186-2"),
+        [
+            "SigGenPSS_186-2.rsp",
+            "SigGenPSS_186-3.rsp",
+        ],
+        b"SHA1"
+    )
+
+
+@pytest.mark.supported(
+    only_if=lambda backend: backend.mgf1_hash_supported(hashes.SHA224()),
+    skip_message="Does not support SHA224 with MGF1."
+)
+@pytest.mark.rsa
+class TestRSAPSSMGF1VerificationSHA224(object):
+    test_rsa_pss_mgf1_sha224 = generate_rsa_pss_test(
+        load_rsa_nist_vectors,
+        os.path.join("asymmetric", "RSA", "FIPS_186-2"),
+        [
+            "SigGenPSS_186-2.rsp",
+            "SigGenPSS_186-3.rsp",
+        ],
+        b"SHA224"
+    )
+
+
+@pytest.mark.supported(
+    only_if=lambda backend: backend.mgf1_hash_supported(hashes.SHA256()),
+    skip_message="Does not support SHA256 with MGF1."
+)
+@pytest.mark.rsa
+class TestRSAPSSMGF1VerificationSHA256(object):
+    test_rsa_pss_mgf1_sha256 = generate_rsa_pss_test(
+        load_rsa_nist_vectors,
+        os.path.join("asymmetric", "RSA", "FIPS_186-2"),
+        [
+            "SigGenPSS_186-2.rsp",
+            "SigGenPSS_186-3.rsp",
+        ],
+        b"SHA256"
+    )
+
+
+@pytest.mark.supported(
+    only_if=lambda backend: backend.mgf1_hash_supported(hashes.SHA384()),
+    skip_message="Does not support SHA384 with MGF1."
+)
+@pytest.mark.rsa
+class TestRSAPSSMGF1VerificationSHA384(object):
+    test_rsa_pss_mgf1_sha384 = generate_rsa_pss_test(
+        load_rsa_nist_vectors,
+        os.path.join("asymmetric", "RSA", "FIPS_186-2"),
+        [
+            "SigGenPSS_186-2.rsp",
+            "SigGenPSS_186-3.rsp",
+        ],
+        b"SHA384"
+    )
+
+
+@pytest.mark.supported(
+    only_if=lambda backend: backend.mgf1_hash_supported(hashes.SHA512()),
+    skip_message="Does not support SHA512 with MGF1."
+)
+@pytest.mark.rsa
+class TestRSAPSSMGF1VerificationSHA512(object):
+    test_rsa_pss_mgf1_sha512 = generate_rsa_pss_test(
+        load_rsa_nist_vectors,
+        os.path.join("asymmetric", "RSA", "FIPS_186-2"),
+        [
+            "SigGenPSS_186-2.rsp",
+            "SigGenPSS_186-3.rsp",
+        ],
+        b"SHA512"
+    )
+
 
 class TestMGF1(object):
     def test_invalid_hash_algorithm(self):
diff --git a/tests/hazmat/primitives/utils.py b/tests/hazmat/primitives/utils.py
index f0a0031..38f6704 100644
--- a/tests/hazmat/primitives/utils.py
+++ b/tests/hazmat/primitives/utils.py
@@ -21,6 +21,7 @@
 import pytest
 
 from cryptography.hazmat.primitives import hashes, hmac
+from cryptography.hazmat.primitives.asymmetric import rsa, padding
 from cryptography.hazmat.primitives.kdf.pbkdf2 import PBKDF2HMAC
 from cryptography.hazmat.primitives.ciphers import Cipher
 from cryptography.hazmat.primitives.kdf.hkdf import HKDF
@@ -373,3 +374,35 @@
         hkdf_test(backend, algorithm, params)
 
     return test_hkdf
+
+
+def generate_rsa_pss_test(param_loader, path, file_names, hash_name):
+    all_params = _load_all_params(path, file_names, param_loader)
+    all_params = [i for i in all_params if i["algorithm"] == hash_name]
+
+    @pytest.mark.parametrize("params", all_params)
+    def test_rsa_pss(self, backend, params):
+        rsa_pss_test(backend, params)
+
+    return test_rsa_pss
+
+
+def rsa_pss_test(backend, params):
+        public_key = rsa.RSAPublicKey(
+            public_exponent=params["public_exponent"],
+            modulus=params["modulus"]
+        )
+        hash_cls = getattr(hashes, params["algorithm"].decode("utf8"))
+        verifier = public_key.verifier(
+            binascii.unhexlify(params["s"]),
+            padding.PSS(
+                mgf=padding.MGF1(
+                    algorithm=hash_cls(),
+                    salt_length=params["salt_length"]
+                )
+            ),
+            hash_cls(),
+            backend
+        )
+        verifier.update(binascii.unhexlify(params["msg"]))
+        verifier.verify()