diff --git a/src/cryptography/hazmat/primitives/ciphers/algorithms.py b/src/cryptography/hazmat/primitives/ciphers/algorithms.py
index 99a837e..68a9e33 100644
--- a/src/cryptography/hazmat/primitives/ciphers/algorithms.py
+++ b/src/cryptography/hazmat/primitives/ciphers/algorithms.py
@@ -12,6 +12,9 @@
 
 
 def _verify_key_size(algorithm, key):
+    # Verify that the key is instance of bytes
+    utils._check_bytes("key", key)
+
     # Verify that the key size matches the expected key size
     if len(key) * 8 not in algorithm.key_sizes:
         raise ValueError("Invalid key size ({0}) for {1}.".format(
diff --git a/tests/hazmat/primitives/test_chacha20.py b/tests/hazmat/primitives/test_chacha20.py
index 16ef97e..33730d9 100644
--- a/tests/hazmat/primitives/test_chacha20.py
+++ b/tests/hazmat/primitives/test_chacha20.py
@@ -58,3 +58,7 @@
 
         with pytest.raises(TypeError):
             algorithms.ChaCha20(b"0" * 32, object())
+
+    def test_invalid_key_type(self):
+        with pytest.raises(TypeError, match="key must be bytes"):
+            algorithms.ChaCha20(u"0" * 32, b"0" * 16)
diff --git a/tests/hazmat/primitives/test_ciphers.py b/tests/hazmat/primitives/test_ciphers.py
index 2f58c9f..f29ba9a 100644
--- a/tests/hazmat/primitives/test_ciphers.py
+++ b/tests/hazmat/primitives/test_ciphers.py
@@ -36,6 +36,10 @@
         with pytest.raises(ValueError):
             AES(binascii.unhexlify(b"0" * 12))
 
+    def test_invalid_key_type(self):
+        with pytest.raises(TypeError, match="key must be bytes"):
+            AES(u"0" * 32)
+
 
 class TestAESXTS(object):
     @pytest.mark.requires_backend_interface(interface=CipherBackend)
@@ -75,6 +79,10 @@
         with pytest.raises(ValueError):
             Camellia(binascii.unhexlify(b"0" * 12))
 
+    def test_invalid_key_type(self):
+        with pytest.raises(TypeError, match="key must be bytes"):
+            Camellia(u"0" * 32)
+
 
 class TestTripleDES(object):
     @pytest.mark.parametrize("key", [
@@ -90,6 +98,10 @@
         with pytest.raises(ValueError):
             TripleDES(binascii.unhexlify(b"0" * 12))
 
+    def test_invalid_key_type(self):
+        with pytest.raises(TypeError, match="key must be bytes"):
+            TripleDES(u"0" * 16)
+
 
 class TestBlowfish(object):
     @pytest.mark.parametrize(("key", "keysize"), [
@@ -103,6 +115,10 @@
         with pytest.raises(ValueError):
             Blowfish(binascii.unhexlify(b"0" * 6))
 
+    def test_invalid_key_type(self):
+        with pytest.raises(TypeError, match="key must be bytes"):
+            Blowfish(u"0" * 8)
+
 
 class TestCAST5(object):
     @pytest.mark.parametrize(("key", "keysize"), [
@@ -116,6 +132,10 @@
         with pytest.raises(ValueError):
             CAST5(binascii.unhexlify(b"0" * 34))
 
+    def test_invalid_key_type(self):
+        with pytest.raises(TypeError, match="key must be bytes"):
+            CAST5(u"0" * 10)
+
 
 class TestARC4(object):
     @pytest.mark.parametrize(("key", "keysize"), [
@@ -135,6 +155,10 @@
         with pytest.raises(ValueError):
             ARC4(binascii.unhexlify(b"0" * 34))
 
+    def test_invalid_key_type(self):
+        with pytest.raises(TypeError, match="key must be bytes"):
+            ARC4(u"0" * 10)
+
 
 class TestIDEA(object):
     def test_key_size(self):
@@ -145,6 +169,10 @@
         with pytest.raises(ValueError):
             IDEA(b"\x00" * 17)
 
+    def test_invalid_key_type(self):
+        with pytest.raises(TypeError, match="key must be bytes"):
+            IDEA(u"0" * 16)
+
 
 class TestSEED(object):
     def test_key_size(self):
@@ -155,6 +183,10 @@
         with pytest.raises(ValueError):
             SEED(b"\x00" * 17)
 
+    def test_invalid_key_type(self):
+        with pytest.raises(TypeError, match="key must be bytes"):
+            SEED(u"0" * 16)
+
 
 def test_invalid_backend():
     pretend_backend = object()