diff --git a/cryptography/exceptions.py b/cryptography/exceptions.py
new file mode 100644
index 0000000..1821ceb
--- /dev/null
+++ b/cryptography/exceptions.py
@@ -0,0 +1,15 @@
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#    http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+# implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+class NoSuchAlgorithm(Exception):
+    pass
diff --git a/cryptography/hazmat/bindings/openssl/backend.py b/cryptography/hazmat/bindings/openssl/backend.py
index fc73dd3..ce8c6a5 100644
--- a/cryptography/hazmat/bindings/openssl/backend.py
+++ b/cryptography/hazmat/bindings/openssl/backend.py
@@ -18,6 +18,7 @@
 
 import cffi
 
+from cryptography.exceptions import NoSuchAlgorithm
 from cryptography.hazmat.primitives import interfaces
 from cryptography.hazmat.primitives.block.ciphers import (
     AES, Blowfish, Camellia, CAST5, TripleDES,
@@ -128,9 +129,12 @@
         ctx = self._backend.ffi.gc(ctx, self._backend.lib.EVP_CIPHER_CTX_free)
 
         registry = self._backend.ciphers._cipher_registry
-        evp_cipher = registry[type(cipher), type(mode)](
-            self._backend, cipher, mode
-        )
+        try:
+            adapter = registry[type(cipher), type(mode)]
+        except KeyError:
+            raise NoSuchAlgorithm
+
+        evp_cipher = adapter(self._backend, cipher, mode)
         assert evp_cipher != self._backend.ffi.NULL
         if isinstance(mode, interfaces.ModeWithInitializationVector):
             iv_nonce = mode.initialization_vector
diff --git a/docs/exceptions.rst b/docs/exceptions.rst
new file mode 100644
index 0000000..b391e62
--- /dev/null
+++ b/docs/exceptions.rst
@@ -0,0 +1,9 @@
+Exceptions
+==========
+
+.. currentmodule:: cryptography.exceptions
+
+.. class:: NoSuchAlgorithm
+
+    This is raised when a backend doesn't support the requested algorithm (or
+    combination of algorithms).
diff --git a/docs/hazmat/primitives/symmetric-encryption.rst b/docs/hazmat/primitives/symmetric-encryption.rst
index b8b1c83..48bad92 100644
--- a/docs/hazmat/primitives/symmetric-encryption.rst
+++ b/docs/hazmat/primitives/symmetric-encryption.rst
@@ -42,12 +42,21 @@
             :class:`~cryptography.hazmat.primitives.interfaces.CipherContext`
             provider.
 
+        If the backend doesn't support the requested combination of ``cipher``
+        and ``mode`` a :class:`cryptography.exceptions.NoSuchAlgorithm` will
+        be raised.
+
     .. method:: decryptor()
 
         :return: A decrypting
             :class:`~cryptography.hazmat.primitives.interfaces.CipherContext`
             provider.
 
+        If the backend doesn't support the requested combination of ``cipher``
+        and ``mode`` a :class:`cryptography.exceptions.NoSuchAlgorithm` will
+        be raised.
+
+
 .. currentmodule:: cryptography.hazmat.primitives.interfaces
 
 .. class:: CipherContext
diff --git a/docs/index.rst b/docs/index.rst
index 4fd5d3b..eb30b5d 100644
--- a/docs/index.rst
+++ b/docs/index.rst
@@ -31,6 +31,7 @@
     :maxdepth: 2
 
     architecture
+    exceptions
     contributing
     security
     community
diff --git a/tests/hazmat/primitives/test_block.py b/tests/hazmat/primitives/test_block.py
index e0ed669..2c0be1b 100644
--- a/tests/hazmat/primitives/test_block.py
+++ b/tests/hazmat/primitives/test_block.py
@@ -17,6 +17,7 @@
 
 import pytest
 
+from cryptography.exceptions import NoSuchAlgorithm
 from cryptography.hazmat.primitives import interfaces
 from cryptography.hazmat.primitives.block import BlockCipher, ciphers, modes
 
@@ -84,3 +85,13 @@
         assert len(pt) == 80
         assert pt == b"a" * 80
         decryptor.finalize()
+
+    def test_nonexistant_cipher(self, backend):
+        cipher = BlockCipher(
+            object(), object(), backend
+        )
+        with pytest.raises(NoSuchAlgorithm):
+            cipher.encryptor()
+
+        with pytest.raises(NoSuchAlgorithm):
+            cipher.decryptor()