diff --git a/.travis.yml b/.travis.yml
index 2c120d2..5c83f88 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -66,6 +66,11 @@
   - python: "pypy3.5-5.10.1"
     env: TOXENV=pypy3-cryptographyMinimum
 
+  # Run tests in random order
+  - python: "2.7"
+    env: TOXENV=py27-randomorder
+  - python: "3.7"
+    env: TOXENV=py37-randomorder
 
   # Make sure we don't break Twisted or urllib3
   - python: "2.7"
diff --git a/tox.ini b/tox.ini
index 8bef9e3..faecfbf 100644
--- a/tox.ini
+++ b/tox.ini
@@ -1,5 +1,5 @@
 [tox]
-envlist = {pypy,pypy3,py27,py34,py35,py36,py37}{,-cryptographyMaster,-cryptographyMinimum},py27-twistedMaster,pypi-readme,check-manifest,flake8,docs,coverage-report
+envlist = {pypy,pypy3,py27,py34,py35,py36,py37}{,-cryptographyMaster,-cryptographyMinimum}{,-randomorder},py27-twistedMaster,pypi-readme,check-manifest,flake8,docs,coverage-report
 
 [testenv]
 whitelist_externals =
@@ -11,6 +11,7 @@
     coverage>=4.2
     cryptographyMaster: git+https://github.com/pyca/cryptography.git
     cryptographyMinimum: cryptography==2.3.0
+    randomorder: pytest-randomly
 setenv =
     # Do not allow the executing environment to pollute the test environment
     # with extra packages.