diff --git a/CHANGELOG.rst b/CHANGELOG.rst
index ef6dffe..c9ea7fa 100644
--- a/CHANGELOG.rst
+++ b/CHANGELOG.rst
@@ -47,6 +47,9 @@
   a single-valued RDN.
 * Added
   :func:`~cryptography.hazmat.primitives.asymmetric.ec.derive_private_key`.
+* Added support for signing and verifying RSA signatures with
+  :class:`~cryptography.hazmat.primitives.asymmetric.utils.Prehashed`
+  digests.
 
 1.5.3 - 2016-11-05
 ~~~~~~~~~~~~~~~~~~
diff --git a/docs/hazmat/primitives/asymmetric/rsa.rst b/docs/hazmat/primitives/asymmetric/rsa.rst
index b6acab6..6cf0e49 100644
--- a/docs/hazmat/primitives/asymmetric/rsa.rst
+++ b/docs/hazmat/primitives/asymmetric/rsa.rst
@@ -703,6 +703,9 @@
     .. method:: verify(signature, data, padding, algorithm)
 
         .. versionadded:: 1.4
+        .. versionchanged:: 1.6
+            :class:`~cryptography.hazmat.primitives.asymmetric.utils.Prehashed`
+            can now be used as an ``algorithm``.
 
         Verify one block of data was signed by the private key
         associated with this public key.
@@ -715,7 +718,9 @@
             :class:`~cryptography.hazmat.primitives.asymmetric.padding.AsymmetricPadding`.
 
         :param algorithm: An instance of
-            :class:`~cryptography.hazmat.primitives.hashes.HashAlgorithm`.
+            :class:`~cryptography.hazmat.primitives.hashes.HashAlgorithm` or
+            :class:`~cryptography.hazmat.primitives.asymmetric.utils.Prehashed`
+            if the ``data`` you want to sign has already been hashed.
 
         :raises cryptography.exceptions.InvalidSignature: If the signature does
             not validate.
diff --git a/docs/hazmat/primitives/asymmetric/utils.rst b/docs/hazmat/primitives/asymmetric/utils.rst
index f29b3e9..ab49e55 100644
--- a/docs/hazmat/primitives/asymmetric/utils.rst
+++ b/docs/hazmat/primitives/asymmetric/utils.rst
@@ -35,7 +35,9 @@
 
     ``Prehashed`` can be passed as the ``algorithm`` in
     :meth:`~cryptography.hazmat.primitives.asymmetric.rsa.RSAPrivateKey.sign`
-    if the data to be signed has been hashed beforehand.
+    or
+    :meth:`~cryptography.hazmat.primitives.asymmetric.rsa.RSAPublicKey.verify`
+    if the data to be signed or verified has been hashed beforehand.
 
     :param algorithm: An instance of
         :class:`~cryptography.hazmat.primitives.hashes.HashAlgorithm`.
@@ -62,3 +64,13 @@
         ...     ),
         ...     utils.Prehashed(hashes.SHA256())
         ... )
+        >>> public_key = private_key.public_key()
+        >>> public_key.verify(
+        ...     signature,
+        ...     prehashed_msg,
+        ...     padding.PSS(
+        ...         mgf=padding.MGF1(hashes.SHA256()),
+        ...         salt_length=padding.PSS.MAX_LENGTH
+        ...     ),
+        ...     utils.Prehashed(hashes.SHA256())
+        ... )
diff --git a/src/cryptography/hazmat/backends/openssl/rsa.py b/src/cryptography/hazmat/backends/openssl/rsa.py
index 85d0652..8996d88 100644
--- a/src/cryptography/hazmat/backends/openssl/rsa.py
+++ b/src/cryptography/hazmat/backends/openssl/rsa.py
@@ -10,10 +10,12 @@
 from cryptography.exceptions import (
     InvalidSignature, UnsupportedAlgorithm, _Reasons
 )
+from cryptography.hazmat.backends.openssl.utils import (
+    _calculate_digest_and_algorithm
+)
 from cryptography.hazmat.primitives import hashes
 from cryptography.hazmat.primitives.asymmetric import (
-    AsymmetricSignatureContext, AsymmetricVerificationContext, rsa,
-    utils as asym_utils
+    AsymmetricSignatureContext, AsymmetricVerificationContext, rsa
 )
 from cryptography.hazmat.primitives.asymmetric.padding import (
     AsymmetricPadding, MGF1, OAEP, PKCS1v15, PSS, calculate_max_pss_salt_length
@@ -453,19 +455,9 @@
         padding_enum = _rsa_sig_determine_padding(
             self._backend, self, padding, algorithm
         )
-        if not isinstance(algorithm, asym_utils.Prehashed):
-            hash_ctx = hashes.Hash(algorithm, self._backend)
-            hash_ctx.update(data)
-            data = hash_ctx.finalize()
-        else:
-            algorithm = algorithm._algorithm
-
-        if len(data) != algorithm.digest_size:
-            raise ValueError(
-                "The provided data must be the same length as the hash "
-                "algorithm's digest size."
-            )
-
+        data, algorithm = _calculate_digest_and_algorithm(
+            self._backend, data, algorithm
+        )
         return _rsa_sig_sign(
             self._backend, padding, padding_enum,
             algorithm, self, data
@@ -523,6 +515,13 @@
         )
 
     def verify(self, signature, data, padding, algorithm):
-        verifier = self.verifier(signature, padding, algorithm)
-        verifier.update(data)
-        verifier.verify()
+        padding_enum = _rsa_sig_determine_padding(
+            self._backend, self, padding, algorithm
+        )
+        data, algorithm = _calculate_digest_and_algorithm(
+            self._backend, data, algorithm
+        )
+        return _rsa_sig_verify(
+            self._backend, padding, padding_enum, algorithm, self,
+            signature, data
+        )
diff --git a/src/cryptography/hazmat/backends/openssl/utils.py b/src/cryptography/hazmat/backends/openssl/utils.py
index 001121f..c88e318 100644
--- a/src/cryptography/hazmat/backends/openssl/utils.py
+++ b/src/cryptography/hazmat/backends/openssl/utils.py
@@ -6,6 +6,9 @@
 
 import six
 
+from cryptography.hazmat.primitives import hashes
+from cryptography.hazmat.primitives.asymmetric.utils import Prehashed
+
 
 def _truncate_digest(digest, order_bits):
     digest_len = len(digest)
@@ -24,3 +27,20 @@
         digest = digest[:-1] + six.int2byte(six.indexbytes(digest, -1) & mask)
 
     return digest
+
+
+def _calculate_digest_and_algorithm(backend, data, algorithm):
+    if not isinstance(algorithm, Prehashed):
+        hash_ctx = hashes.Hash(algorithm, backend)
+        hash_ctx.update(data)
+        data = hash_ctx.finalize()
+    else:
+        algorithm = algorithm._algorithm
+
+    if len(data) != algorithm.digest_size:
+        raise ValueError(
+            "The provided data must be the same length as the hash "
+            "algorithm's digest size."
+        )
+
+    return (data, algorithm)
diff --git a/tests/hazmat/primitives/test_rsa.py b/tests/hazmat/primitives/test_rsa.py
index 6ec1799..cbb9be6 100644
--- a/tests/hazmat/primitives/test_rsa.py
+++ b/tests/hazmat/primitives/test_rsa.py
@@ -897,6 +897,29 @@
         public_key = private_key.public_key()
         public_key.verify(signature, message, pkcs, algorithm)
 
+    def test_prehashed_verify(self, backend):
+        private_key = RSA_KEY_512.private_key(backend)
+        message = b"one little message"
+        h = hashes.Hash(hashes.SHA1(), backend)
+        h.update(message)
+        digest = h.finalize()
+        prehashed_alg = asym_utils.Prehashed(hashes.SHA1())
+        pkcs = padding.PKCS1v15()
+        signature = private_key.sign(message, pkcs, hashes.SHA1())
+        public_key = private_key.public_key()
+        public_key.verify(signature, digest, pkcs, prehashed_alg)
+
+    def test_prehashed_digest_mismatch(self, backend):
+        public_key = RSA_KEY_512.private_key(backend).public_key()
+        message = b"one little message"
+        h = hashes.Hash(hashes.SHA1(), backend)
+        h.update(message)
+        data = h.finalize()
+        prehashed_alg = asym_utils.Prehashed(hashes.SHA512())
+        pkcs = padding.PKCS1v15()
+        with pytest.raises(ValueError):
+            public_key.verify(b"\x00" * 64, data, pkcs, prehashed_alg)
+
 
 @pytest.mark.requires_backend_interface(interface=RSABackend)
 class TestRSAPSSMGF1Verification(object):