diff --git a/cryptography/hazmat/backends/openssl/backend.py b/cryptography/hazmat/backends/openssl/backend.py
index 588a427..714823e 100644
--- a/cryptography/hazmat/backends/openssl/backend.py
+++ b/cryptography/hazmat/backends/openssl/backend.py
@@ -288,11 +288,19 @@
         try:
             adapter = registry[type(cipher), type(mode)]
         except KeyError:
-            raise UnsupportedAlgorithm
+            raise UnsupportedAlgorithm(
+                "cipher {0} in {1} mode is not supported "
+                "by this backend".format(
+                    cipher.name, mode.name if mode else mode)
+            )
 
         evp_cipher = adapter(self._backend, cipher, mode)
         if evp_cipher == self._backend.ffi.NULL:
-            raise UnsupportedAlgorithm
+            raise UnsupportedAlgorithm(
+                "cipher {0} in {1} mode is not supported "
+                "by this backend".format(
+                    cipher.name, mode.name if mode else mode)
+            )
 
         if isinstance(mode, interfaces.ModeWithInitializationVector):
             iv_nonce = mode.initialization_vector
diff --git a/docs/hazmat/primitives/symmetric-encryption.rst b/docs/hazmat/primitives/symmetric-encryption.rst
index f4d0457..dfadd89 100644
--- a/docs/hazmat/primitives/symmetric-encryption.rst
+++ b/docs/hazmat/primitives/symmetric-encryption.rst
@@ -61,7 +61,7 @@
             provider.
 
         If the backend doesn't support the requested combination of ``cipher``
-        and ``mode`` an :class:`cryptography.exceptions.UnsupportedAlgorithm`
+        and ``mode`` an :class:`~cryptography.exceptions.UnsupportedAlgorithm`
         will be raised.
 
     .. method:: decryptor()
diff --git a/tests/hazmat/backends/test_openssl.py b/tests/hazmat/backends/test_openssl.py
index 962959b..543a05f 100644
--- a/tests/hazmat/backends/test_openssl.py
+++ b/tests/hazmat/backends/test_openssl.py
@@ -23,13 +23,14 @@
 from cryptography.hazmat.primitives.ciphers.modes import CBC
 
 
+@utils.register_interface(interfaces.Mode)
 class DummyMode(object):
-    pass
+    name = "dummy-mode"
 
 
 @utils.register_interface(interfaces.CipherAlgorithm)
 class DummyCipher(object):
-    pass
+    name = "dummy-cipher"
 
 
 class TestOpenSSL(object):
@@ -62,15 +63,16 @@
         assert b.ffi is backend.ffi
         assert b.lib is backend.lib
 
-    def test_nonexistent_cipher(self):
+    @pytest.mark.parametrize("mode", [DummyMode(), None])
+    def test_nonexistent_cipher(self, mode):
         b = Backend()
         b.register_cipher_adapter(
             DummyCipher,
-            DummyMode,
+            type(mode),
             lambda backend, cipher, mode: backend.ffi.NULL
         )
         cipher = Cipher(
-            DummyCipher(), DummyMode(), backend=b,
+            DummyCipher(), mode, backend=b,
         )
         with pytest.raises(UnsupportedAlgorithm):
             cipher.encryptor()
diff --git a/tests/hazmat/primitives/test_block.py b/tests/hazmat/primitives/test_block.py
index 02de386..573f563 100644
--- a/tests/hazmat/primitives/test_block.py
+++ b/tests/hazmat/primitives/test_block.py
@@ -31,9 +31,14 @@
 )
 
 
+@utils.register_interface(interfaces.Mode)
+class DummyMode(object):
+    name = "dummy-mode"
+
+
 @utils.register_interface(interfaces.CipherAlgorithm)
 class DummyCipher(object):
-    pass
+    name = "dummy-cipher"
 
 
 class TestCipher(object):
@@ -101,9 +106,10 @@
         assert pt == b"a" * 80
         decryptor.finalize()
 
-    def test_nonexistent_cipher(self, backend):
+    @pytest.mark.parametrize("mode", [DummyMode(), None])
+    def test_nonexistent_cipher(self, backend, mode):
         cipher = Cipher(
-            DummyCipher(), object(), backend
+            DummyCipher(), mode, backend
         )
         with pytest.raises(UnsupportedAlgorithm):
             cipher.encryptor()