diff --git a/tests/hazmat/primitives/test_padding.py b/tests/hazmat/primitives/test_padding.py
index e934c0a..fb72a79 100644
--- a/tests/hazmat/primitives/test_padding.py
+++ b/tests/hazmat/primitives/test_padding.py
@@ -6,6 +6,8 @@
 
 import pytest
 
+import six
+
 from cryptography.exceptions import AlreadyFinalized
 from cryptography.hazmat.primitives import padding
 
@@ -100,6 +102,20 @@
         with pytest.raises(AlreadyFinalized):
             unpadder.finalize()
 
+    def test_large_padding(self):
+        padder = padding.PKCS7(2040).padder()
+        padded_data = padder.update(b"")
+        padded_data += padder.finalize()
+
+        for i in six.iterbytes(padded_data):
+            assert i == 255
+
+        unpadder = padding.PKCS7(2040).unpadder()
+        data = unpadder.update(padded_data)
+        data += unpadder.finalize()
+
+        assert data == b""
+
 
 class TestANSIX923(object):
     @pytest.mark.parametrize("size", [127, 4096, -2])
diff --git a/tests/hypothesis/test_padding.py b/tests/hypothesis/test_padding.py
index 29d726f..a433391 100644
--- a/tests/hypothesis/test_padding.py
+++ b/tests/hypothesis/test_padding.py
@@ -8,7 +8,7 @@
 from cryptography.hazmat.primitives.padding import ANSIX923, PKCS7
 
 
-@given(integers(min_value=1, max_value=31), binary())
+@given(integers(min_value=1, max_value=255), binary())
 def test_pkcs7(block_size, data):
     # Generate in [1, 31] so we can easily get block_size in bits by
     # multiplying by 8.
@@ -21,7 +21,7 @@
     assert unpadder.update(padded) + unpadder.finalize() == data
 
 
-@given(integers(min_value=1, max_value=31), binary())
+@given(integers(min_value=1, max_value=255), binary())
 def test_ansix923(block_size, data):
     a = ANSIX923(block_size=block_size * 8)
     padder = a.padder()