diff --git a/.travis.yml b/.travis.yml
index 8fda670..2a636ad 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -29,6 +29,8 @@
           env: TOXENV=py36
         - python: 3.7
           env: TOXENV=py37
+        - python: 3.7
+          env: TOXENV=py37-idna
         - python: pypy-5.3
           env: TOXENV=pypy-nocoverage
           # PyPy 5.3 isn't available for xenial
@@ -121,10 +123,9 @@
         - python: 2.7
           env: DOWNSTREAM=aws-encryption-sdk
         - python: 2.7
-          env: DOWNSTREAM=dynamodb-encryption-sdk OPENSSL=1.1.0j
-          # dynamodb-encryption-sdk tests fail on xenial for whatever reason
-          dist: trusty
-          sudo: false
+          # BOTO_CONFIG works around this boto issue on travis:
+          # https://github.com/boto/boto/issues/3717
+          env: DOWNSTREAM=dynamodb-encryption-sdk OPENSSL=1.1.0j BOTO_CONFIG=/dev/null
         - python: 2.7
           env: DOWNSTREAM=certbot OPENSSL=1.1.0j
         - python: 2.7
diff --git a/CHANGELOG.rst b/CHANGELOG.rst
index b75836d..eb7a4d8 100644
--- a/CHANGELOG.rst
+++ b/CHANGELOG.rst
@@ -8,6 +8,10 @@
 
 .. note:: This version is not yet released and is under active development.
 
+* **BACKWARDS INCOMPATIBLE:** :term:`U-label` strings were deprecated in
+  version 2.1, but this version removes the default ``idna`` dependency as
+  well. If you still need this deprecated path please install cryptography
+  with the ``idna`` extra: ``pip install cryptography[idna]``.
 * Added support for :class:`~cryptography.hazmat.primitives.hashes.SHA512_224`
   and :class:`~cryptography.hazmat.primitives.hashes.SHA512_256` when using
   OpenSSL 1.1.1.
diff --git a/docs/faq.rst b/docs/faq.rst
index 409f6ce..dce94b7 100644
--- a/docs/faq.rst
+++ b/docs/faq.rst
@@ -99,6 +99,18 @@
 with any version of Python greater than or equal to 3.4. Recent versions of
 ``pip`` will automatically install ``abi3`` wheels.
 
+``ImportError``: ``idna`` is not installed
+------------------------------------------
+
+``cryptography`` deprecated passing :term:`U-label` strings to various X.509
+constructors in version 2.1 and in version 2.5 moved the ``idna`` dependency
+to a ``setuptools`` extra. If you see this exception you should upgrade your
+software so that it no longer depends on this deprecated feature. If that is
+not yet possible you  can also install ``cryptography`` with
+``pip install cryptography[idna]`` to automatically install the missing
+dependency. This workaround will be available until the feature is fully
+removed.
+
 .. _`NaCl`: https://nacl.cr.yp.to/
 .. _`PyNaCl`: https://pynacl.readthedocs.io
 .. _`WSGIApplicationGroup`: https://modwsgi.readthedocs.io/en/develop/configuration-directives/WSGIApplicationGroup.html
diff --git a/setup.py b/setup.py
index 937d1ac..bd98fd5 100644
--- a/setup.py
+++ b/setup.py
@@ -287,7 +287,6 @@
     python_requires='>=2.7,!=3.0.*,!=3.1.*,!=3.2.*,!=3.3.*',
 
     install_requires=[
-        "idna >= 2.1",
         "asn1crypto >= 0.21.0",
         "six >= 1.4.1",
     ] + setup_requirements,
@@ -311,6 +310,12 @@
             "flake8-import-order",
             "pep8-naming",
         ],
+        # This extra is for the U-label support that was deprecated in
+        # cryptography 2.1. If you need this deprecated path install with
+        # pip install cryptography[idna]
+        "idna": [
+            "idna >= 2.1",
+        ]
     },
 
     # for cffi
diff --git a/src/cryptography/x509/general_name.py b/src/cryptography/x509/general_name.py
index 4208274..1b0f8c8 100644
--- a/src/cryptography/x509/general_name.py
+++ b/src/cryptography/x509/general_name.py
@@ -30,6 +30,20 @@
 }
 
 
+def _lazy_import_idna():
+    # Import idna lazily becase it allocates a decent amount of memory, and
+    # we're only using it in deprecated paths.
+    try:
+        import idna
+        return idna
+    except ImportError:
+        raise ImportError(
+            "idna is not installed, but a deprecated feature that requires it"
+            " was used. See: https://cryptography.io/en/latest/faq/#importe"
+            "rror-idna-is-not-installed"
+        )
+
+
 class UnsupportedGeneralNameType(Exception):
     def __init__(self, msg, type):
         super(UnsupportedGeneralNameType, self).__init__(msg)
@@ -81,10 +95,7 @@
         return instance
 
     def _idna_encode(self, value):
-        # Import idna lazily becase it allocates a decent amoutn of memory, and
-        # we're only using it in deprecated paths.
-        import idna
-
+        idna = _lazy_import_idna()
         _, address = parseaddr(value)
         parts = address.split(u"@")
         return parts[0] + "@" + idna.encode(parts[1]).decode("ascii")
@@ -106,10 +117,7 @@
 
 
 def _idna_encode(value):
-    # Import idna lazily becase it allocates a decent amoutn of memory, and
-    # we're only using it in deprecated paths.
-    import idna
-
+    idna = _lazy_import_idna()
     # Retain prefixes '*.' for common/alt names and '.' for name constraints
     for prefix in ['*.', '.']:
         if value.startswith(prefix):
@@ -193,10 +201,7 @@
         return instance
 
     def _idna_encode(self, value):
-        # Import idna lazily becase it allocates a decent amoutn of memory, and
-        # we're only using it in deprecated paths.
-        import idna
-
+        idna = _lazy_import_idna()
         parsed = urllib_parse.urlparse(value)
         if parsed.port:
             netloc = (
diff --git a/tests/x509/test_x509_ext.py b/tests/x509/test_x509_ext.py
index bfa3784..152db96 100644
--- a/tests/x509/test_x509_ext.py
+++ b/tests/x509/test_x509_ext.py
@@ -20,6 +20,7 @@
 from cryptography.hazmat.primitives import hashes
 from cryptography.hazmat.primitives.asymmetric import ec
 from cryptography.x509 import DNSName, NameConstraints, SubjectAlternativeName
+from cryptography.x509.general_name import _lazy_import_idna
 from cryptography.x509.oid import (
     AuthorityInformationAccessOID, ExtendedKeyUsageOID, ExtensionOID,
     NameOID, ObjectIdentifier
@@ -44,6 +45,17 @@
     )
 
 
+def test_lazy_idna_import():
+    try:
+        __import__("idna")
+        pytest.skip("idna is installed")
+    except ImportError:
+        pass
+
+    with pytest.raises(ImportError):
+        _lazy_import_idna()
+
+
 class TestExtension(object):
     def test_not_an_oid(self):
         bc = x509.BasicConstraints(ca=False, path_length=None)
@@ -1661,10 +1673,8 @@
 
 
 class TestDNSName(object):
-    def test_init(self):
-        name = x509.DNSName(u"*.xn--4ca7aey.example.com")
-        assert name.value == u"*.xn--4ca7aey.example.com"
-
+    def test_init_deprecated(self):
+        pytest.importorskip("idna")
         with pytest.warns(utils.DeprecatedIn21):
             name = x509.DNSName(u".\xf5\xe4\xf6\xfc.example.com")
         assert name.value == u".xn--4ca7aey.example.com"
@@ -1673,6 +1683,10 @@
             name = x509.DNSName(u"\xf5\xe4\xf6\xfc.example.com")
         assert name.value == u"xn--4ca7aey.example.com"
 
+    def test_init(self):
+        name = x509.DNSName(u"*.xn--4ca7aey.example.com")
+        assert name.value == u"*.xn--4ca7aey.example.com"
+
         with pytest.raises(TypeError):
             x509.DNSName(1.3)
 
@@ -1788,6 +1802,7 @@
         assert gn.value == u"administrator"
 
     def test_idna(self):
+        pytest.importorskip("idna")
         with pytest.warns(utils.DeprecatedIn21):
             gn = x509.RFC822Name(u"email@em\xe5\xefl.com")
 
@@ -1827,6 +1842,7 @@
         assert gn.value == u"singlelabel:443/test"
 
     def test_idna_no_port(self):
+        pytest.importorskip("idna")
         with pytest.warns(utils.DeprecatedIn21):
             gn = x509.UniformResourceIdentifier(
                 u"http://\u043f\u044b\u043a\u0430.cryptography"
@@ -1835,6 +1851,7 @@
         assert gn.value == u"http://xn--80ato2c.cryptography"
 
     def test_idna_with_port(self):
+        pytest.importorskip("idna")
         with pytest.warns(utils.DeprecatedIn21):
             gn = x509.UniformResourceIdentifier(
                 u"gopher://\u043f\u044b\u043a\u0430.cryptography:70/some/path"
@@ -1849,6 +1866,7 @@
         assert gn.value == "ldap:///some-nonsense"
 
     def test_query_and_fragment(self):
+        pytest.importorskip("idna")
         with pytest.warns(utils.DeprecatedIn21):
             gn = x509.UniformResourceIdentifier(
                 u"ldap://\u043f\u044b\u043a\u0430.cryptography:90/path?query="
diff --git a/tox.ini b/tox.ini
index f6e1b6e..d4c3022 100644
--- a/tox.ini
+++ b/tox.ini
@@ -5,6 +5,7 @@
 [testenv]
 extras =
    test
+   idna: idna
 deps =
     # This must be kept in sync with Jenkinsfile and .travis/install.sh
     coverage