diff --git a/src/cryptography/hazmat/backends/openssl/x509.py b/src/cryptography/hazmat/backends/openssl/x509.py
index 4125848..c7ca2ad 100644
--- a/src/cryptography/hazmat/backends/openssl/x509.py
+++ b/src/cryptography/hazmat/backends/openssl/x509.py
@@ -86,13 +86,17 @@
             # This is a wildcard name. We need to remove the leading wildcard,
             # IDNA decode, then re-add the wildcard. Wildcard characters should
             # always be left-most (RFC 2595 section 2.4).
-            data = u"*." + idna.decode(data[2:])
+            decoded = u"*." + idna.decode(data[2:])
         else:
             # Not a wildcard, decode away. If the string has a * in it anywhere
             # invalid this will raise an InvalidCodePoint
-            data = idna.decode(data)
+            decoded = idna.decode(data)
+            if data.startswith(b"."):
+                # idna strips leading periods. Name constraints can have that
+                # so we need to re-add it. Sigh.
+                decoded = u"." + decoded
 
-        return x509.DNSName(data)
+        return x509.DNSName(decoded)
     elif gn.type == backend._lib.GEN_URI:
         data = backend._ffi.buffer(
             gn.d.uniformResourceIdentifier.data,
diff --git a/tests/test_x509_ext.py b/tests/test_x509_ext.py
index 15ee118..0ef84e7 100644
--- a/tests/test_x509_ext.py
+++ b/tests/test_x509_ext.py
@@ -2076,6 +2076,44 @@
             excluded_subtrees=None
         )
 
+    def test_permitted_with_leading_period(self, backend):
+        cert = _load_cert(
+            os.path.join(
+                "x509", "custom", "nc_permitted.pem"
+            ),
+            x509.load_pem_x509_certificate,
+            backend
+        )
+        nc = cert.extensions.get_extension_for_oid(
+            x509.OID_NAME_CONSTRAINTS
+        ).value
+        assert nc == x509.NameConstraints(
+            permitted_subtrees=[
+                x509.DNSName(u".cryptography.io"),
+                x509.UniformResourceIdentifier(u"ftp://cryptography.test")
+            ],
+            excluded_subtrees=None
+        )
+
+    def test_excluded_with_leading_period(self, backend):
+        cert = _load_cert(
+            os.path.join(
+                "x509", "custom", "nc_excluded.pem"
+            ),
+            x509.load_pem_x509_certificate,
+            backend
+        )
+        nc = cert.extensions.get_extension_for_oid(
+            x509.OID_NAME_CONSTRAINTS
+        ).value
+        assert nc == x509.NameConstraints(
+            permitted_subtrees=None,
+            excluded_subtrees=[
+                x509.DNSName(u".cryptography.io"),
+                x509.UniformResourceIdentifier(u"gopher://cryptography.test")
+            ]
+        )
+
 
 class TestDistributionPoint(object):
     def test_distribution_point_full_name_not_general_names(self):