diff --git a/cryptography/hazmat/primitives/ciphers/base.py b/cryptography/hazmat/primitives/ciphers/base.py
index 3d733af..d046a01 100644
--- a/cryptography/hazmat/primitives/ciphers/base.py
+++ b/cryptography/hazmat/primitives/ciphers/base.py
@@ -28,6 +28,9 @@
         if not isinstance(algorithm, interfaces.CipherAlgorithm):
             raise TypeError("Expected interface of interfaces.CipherAlgorithm")
 
+        if mode is not None:
+            mode.validate_for_algorithm(algorithm)
+
         self.algorithm = algorithm
         self.mode = mode
         self._backend = backend
diff --git a/cryptography/hazmat/primitives/ciphers/modes.py b/cryptography/hazmat/primitives/ciphers/modes.py
index 1d0de68..597b4e3 100644
--- a/cryptography/hazmat/primitives/ciphers/modes.py
+++ b/cryptography/hazmat/primitives/ciphers/modes.py
@@ -25,11 +25,20 @@
     def __init__(self, initialization_vector):
         self.initialization_vector = initialization_vector
 
+    def validate_for_algorithm(self, algorithm):
+        if len(self.initialization_vector) * 8 != algorithm.block_size:
+            raise ValueError("Invalid iv size ({0}) for {1}".format(
+                len(self.initialization_vector), self.name
+            ))
+
 
 @utils.register_interface(interfaces.Mode)
 class ECB(object):
     name = "ECB"
 
+    def validate_for_algorithm(self, algorithm):
+        pass
+
 
 @utils.register_interface(interfaces.Mode)
 @utils.register_interface(interfaces.ModeWithInitializationVector)
@@ -39,6 +48,12 @@
     def __init__(self, initialization_vector):
         self.initialization_vector = initialization_vector
 
+    def validate_for_algorithm(self, algorithm):
+        if len(self.initialization_vector) * 8 != algorithm.block_size:
+            raise ValueError("Invalid iv size ({0}) for {1}".format(
+                len(self.initialization_vector), self.name
+            ))
+
 
 @utils.register_interface(interfaces.Mode)
 @utils.register_interface(interfaces.ModeWithInitializationVector)
@@ -48,6 +63,12 @@
     def __init__(self, initialization_vector):
         self.initialization_vector = initialization_vector
 
+    def validate_for_algorithm(self, algorithm):
+        if len(self.initialization_vector) * 8 != algorithm.block_size:
+            raise ValueError("Invalid iv size ({0}) for {1}".format(
+                len(self.initialization_vector), self.name
+            ))
+
 
 @utils.register_interface(interfaces.Mode)
 @utils.register_interface(interfaces.ModeWithNonce)
diff --git a/cryptography/hazmat/primitives/interfaces.py b/cryptography/hazmat/primitives/interfaces.py
index 8cc9d42..672ac96 100644
--- a/cryptography/hazmat/primitives/interfaces.py
+++ b/cryptography/hazmat/primitives/interfaces.py
@@ -39,6 +39,13 @@
         A string naming this mode.  (e.g. ECB, CBC)
         """
 
+    @abc.abstractmethod
+    def validate_for_algorithm(self, algorithm):
+        """
+        Checks that all the necessary invariants of this (mode, algorithm)
+        combination are met.
+        """
+
 
 class ModeWithInitializationVector(six.with_metaclass(abc.ABCMeta)):
     @abc.abstractproperty
diff --git a/docs/hazmat/primitives/interfaces.rst b/docs/hazmat/primitives/interfaces.rst
index 11cff51..e798c0e 100644
--- a/docs/hazmat/primitives/interfaces.rst
+++ b/docs/hazmat/primitives/interfaces.rst
@@ -56,6 +56,18 @@
         The name may be used by a backend to influence the operation of a
         cipher in conjunction with the algorithm's name.
 
+    .. method:: validate_for_algorithm(algorithm)
+
+        :param CipherAlgorithm algorithm:
+
+        Checks that the combination of this mode with the provided algorithm
+        meets any necessary invariants. This should raise an exception if they
+        are not met.
+
+        For example, the :class:`~cryptography.hazmat.primitives.modes.CBC`
+        mode uses this method to check that the provided initialization
+        vector's length matches the block size of the algorithm.
+
 
 .. class:: ModeWithInitializationVector
 
diff --git a/tests/hazmat/bindings/test_openssl.py b/tests/hazmat/bindings/test_openssl.py
index 9f27aab..1cadc75 100644
--- a/tests/hazmat/bindings/test_openssl.py
+++ b/tests/hazmat/bindings/test_openssl.py
@@ -23,7 +23,8 @@
 
 
 class DummyMode(object):
-    pass
+    def validate_for_algorithm(self, algorithm):
+        pass
 
 
 @utils.register_interface(interfaces.CipherAlgorithm)
diff --git a/tests/hazmat/primitives/test_block.py b/tests/hazmat/primitives/test_block.py
index 9460c53..b41f892 100644
--- a/tests/hazmat/primitives/test_block.py
+++ b/tests/hazmat/primitives/test_block.py
@@ -30,6 +30,11 @@
     pass
 
 
+class DummyMode(object):
+    def validate_for_algorithm(self, algorithm):
+        pass
+
+
 class TestCipher(object):
     def test_instantiate_without_backend(self):
         Cipher(
@@ -101,10 +106,20 @@
 
     def test_nonexistent_cipher(self, backend):
         cipher = Cipher(
-            DummyCipher(), object(), backend
+            DummyCipher(), DummyMode(), backend
         )
         with pytest.raises(UnsupportedAlgorithm):
             cipher.encryptor()
 
         with pytest.raises(UnsupportedAlgorithm):
             cipher.decryptor()
+
+
+class TestModeValidation(object):
+    def test_cbc(self, backend):
+        with pytest.raises(ValueError):
+            Cipher(
+                algorithms.AES(b"\x00" * 16),
+                modes.CBC(b"abc"),
+                backend,
+            )