diff --git a/docs/hazmat/backends/interfaces.rst b/docs/hazmat/backends/interfaces.rst
index 3a7224f..2952d85 100644
--- a/docs/hazmat/backends/interfaces.rst
+++ b/docs/hazmat/backends/interfaces.rst
@@ -589,6 +589,25 @@
         :returns: A new instance of
             :class:`~cryptography.x509.CertificateRevocationList`.
 
+    .. method:: create_x509_crl(builder, private_key, algorithm)
+
+        .. versionadded:: 1.2
+
+        :param builder: An instance of
+            :class:`~cryptography.x509.CertificateRevocationListBuilder`.
+
+        :param private_key: The
+            :class:`~cryptography.hazmat.primitives.asymmetric.rsa.RSAPrivateKey`,
+            :class:`~cryptography.hazmat.primitives.asymmetric.dsa.DSAPrivateKey` or
+            :class:`~cryptography.hazmat.primitives.asymmetric.ec.EllipticCurvePrivateKey`
+            that will be used to sign the CRL.
+
+        :param algorithm: The
+            :class:`~cryptography.hazmat.primitives.hashes.HashAlgorithm`
+            that will be used to generate the CRL signature.
+
+        :returns: A new object with the
+            :class:`~cryptography.x509.CertificateRevocationList` interface.
 
 .. class:: DHBackend
 
diff --git a/docs/x509/reference.rst b/docs/x509/reference.rst
index 4f4ce4f..0697e63 100644
--- a/docs/x509/reference.rst
+++ b/docs/x509/reference.rst
@@ -761,6 +761,88 @@
         key embedded in the CSR). This data may be used to validate the CSR
         signature.
 
+X.509 Certificate Revocation List Builder
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+.. class:: CertificateRevocationListBuilder
+
+    .. versionadded:: 1.2
+
+    .. doctest::
+
+        >>> from cryptography import x509
+        >>> from cryptography.hazmat.backends import default_backend
+        >>> from cryptography.hazmat.primitives import hashes
+        >>> from cryptography.hazmat.primitives.asymmetric import rsa
+        >>> from cryptography.x509.oid import NameOID
+        >>> import datetime
+        >>> one_day = datetime.timedelta(1, 0, 0)
+        >>> private_key = rsa.generate_private_key(
+        ...     public_exponent=65537,
+        ...     key_size=2048,
+        ...     backend=default_backend()
+        ... )
+        >>> builder = x509.CertificateRevocationListBuilder()
+        >>> builder = builder.issuer_name(x509.Name([
+        ...     x509.NameAttribute(NameOID.COMMON_NAME, u'cryptography.io CA'),
+        ... ]))
+        >>> builder = builder.last_update(datetime.datetime.today())
+        >>> builder = builder.next_update(datetime.datetime.today() + one_day)
+        >>> crl = builder.sign(
+        ...     private_key=private_key, algorithm=hashes.SHA256(),
+        ...     backend=default_backend()
+        ... )
+        >>> isinstance(crl, x509.CertificateRevocationList)
+        True
+
+    .. method:: issuer_name(name)
+
+        Sets the issuer's distinguished name.
+
+        :param name: The :class:`~cryptography.x509.Name` that describes the
+            issuer (CA).
+
+    .. method:: last_update(time)
+
+        Sets the CRL's activation time.  This is the time from which
+        clients can start trusting the CRL.  It may be different from
+        the time at which the CRL was created. This is also known as the
+        ``thisUpdate`` time.
+
+        :param time: The :class:`datetime.datetime` object (in UTC) that marks the
+            activation time for the CRL.  The CRL may not be trusted if it is
+            used before this time.
+
+    .. method:: next_update(time)
+
+        Sets the CRL's next update time. This is the time by which
+        a new CRL will be issued. The next CRL could be issued before this
+        , but it will not be issued any later than the indicated date.
+
+        :param time: The :class:`datetime.datetime` object (in UTC) that marks the
+            next update time for the CRL.
+
+    .. method:: sign(private_key, algorithm, backend)
+
+        Sign the CRL using the CA's private key.
+
+        :param private_key: The
+            :class:`~cryptography.hazmat.primitives.asymmetric.rsa.RSAPrivateKey`,
+            :class:`~cryptography.hazmat.primitives.asymmetric.dsa.DSAPrivateKey` or
+            :class:`~cryptography.hazmat.primitives.asymmetric.ec.EllipticCurvePrivateKey`
+            that will be used to sign the certificate.
+
+        :param algorithm: The
+            :class:`~cryptography.hazmat.primitives.hashes.HashAlgorithm` that
+            will be used to generate the signature.
+
+        :param backend: Backend that will be used to build the CRL.
+            Must support the
+            :class:`~cryptography.hazmat.backends.interfaces.X509Backend`
+            interface.
+
+        :returns: :class:`~cryptography.x509.CertificateRevocationList`
+
 X.509 Revoked Certificate Object
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
diff --git a/src/cryptography/hazmat/backends/openssl/backend.py b/src/cryptography/hazmat/backends/openssl/backend.py
index c3eccb0..6d19b80 100644
--- a/src/cryptography/hazmat/backends/openssl/backend.py
+++ b/src/cryptography/hazmat/backends/openssl/backend.py
@@ -1456,7 +1456,73 @@
         return _Certificate(self, x509_cert)
 
     def create_x509_crl(self, builder, private_key, algorithm):
-        raise NotImplementedError
+        if not isinstance(builder, x509.CertificateRevocationListBuilder):
+            raise TypeError('Builder type mismatch.')
+        if not isinstance(algorithm, hashes.HashAlgorithm):
+            raise TypeError('Algorithm must be a registered hash algorithm.')
+
+        if isinstance(private_key, _DSAPrivateKey):
+            raise NotImplementedError(
+                "CRL signatures aren't implemented for DSA"
+                " keys at this time."
+            )
+        if isinstance(private_key, _EllipticCurvePrivateKey):
+            raise NotImplementedError(
+                "CRL signatures aren't implemented for EC"
+                " keys at this time."
+            )
+
+        evp_md = self._lib.EVP_get_digestbyname(
+            algorithm.name.encode('ascii')
+        )
+        self.openssl_assert(evp_md != self._ffi.NULL)
+
+        # Create an empty CRL.
+        x509_crl = self._lib.X509_CRL_new()
+        x509_crl = self._ffi.gc(x509_crl, backend._lib.X509_CRL_free)
+
+        # Set the x509 CRL version. We only support v2 (integer value 1).
+        res = self._lib.X509_CRL_set_version(x509_crl, 1)
+        self.openssl_assert(res == 1)
+
+        # Set the issuer name.
+        res = self._lib.X509_CRL_set_issuer_name(
+            x509_crl, _encode_name_gc(self, list(builder._issuer_name))
+        )
+        self.openssl_assert(res == 1)
+
+        # Set the last update time.
+        last_update = self._lib.ASN1_TIME_set(
+            self._ffi.NULL, calendar.timegm(builder._last_update.timetuple())
+        )
+        self.openssl_assert(last_update != self._ffi.NULL)
+        last_update = self._ffi.gc(last_update, self._lib.ASN1_TIME_free)
+        res = self._lib.X509_CRL_set_lastUpdate(x509_crl, last_update)
+        self.openssl_assert(res == 1)
+
+        # Set the next update time.
+        next_update = self._lib.ASN1_TIME_set(
+            self._ffi.NULL, calendar.timegm(builder._next_update.timetuple())
+        )
+        self.openssl_assert(next_update != self._ffi.NULL)
+        next_update = self._ffi.gc(next_update, self._lib.ASN1_TIME_free)
+        res = self._lib.X509_CRL_set_nextUpdate(x509_crl, next_update)
+        self.openssl_assert(res == 1)
+        # TODO: support revoked certificates
+
+        # TODO: add support for CRL extensions
+        res = self._lib.X509_CRL_sign(
+            x509_crl, private_key._evp_pkey, evp_md
+        )
+        if res == 0:
+            errors = self._consume_errors()
+            self.openssl_assert(errors[0][1] == self._lib.ERR_LIB_RSA)
+            self.openssl_assert(
+                errors[0][3] == self._lib.RSA_R_DIGEST_TOO_BIG_FOR_RSA_KEY
+            )
+            raise ValueError("Digest too big for RSA key")
+
+        return _CertificateRevocationList(self, x509_crl)
 
     def load_pem_private_key(self, data, password):
         return self._load_key(
diff --git a/src/cryptography/x509/__init__.py b/src/cryptography/x509/__init__.py
index c4434fd..4978b19 100644
--- a/src/cryptography/x509/__init__.py
+++ b/src/cryptography/x509/__init__.py
@@ -6,6 +6,7 @@
 
 from cryptography.x509.base import (
     Certificate, CertificateBuilder, CertificateRevocationList,
+    CertificateRevocationListBuilder,
     CertificateSigningRequest, CertificateSigningRequestBuilder,
     InvalidVersion, RevokedCertificate,
     Version, load_der_x509_certificate, load_der_x509_crl, load_der_x509_csr,
@@ -152,6 +153,7 @@
     "OtherName",
     "Certificate",
     "CertificateRevocationList",
+    "CertificateRevocationListBuilder",
     "CertificateSigningRequest",
     "RevokedCertificate",
     "CertificateSigningRequestBuilder",
diff --git a/src/cryptography/x509/base.py b/src/cryptography/x509/base.py
index 057d0e9..6bca2c5 100644
--- a/src/cryptography/x509/base.py
+++ b/src/cryptography/x509/base.py
@@ -518,3 +518,69 @@
             raise ValueError("A certificate must have a public key")
 
         return backend.create_x509_certificate(self, private_key, algorithm)
+
+
+class CertificateRevocationListBuilder(object):
+    def __init__(self, issuer_name=None, last_update=None, next_update=None,
+                 extensions=[], revoked_certificates=[]):
+        self._issuer_name = issuer_name
+        self._last_update = last_update
+        self._next_update = next_update
+        self._extensions = extensions
+        self._revoked_certificates = revoked_certificates
+
+    def issuer_name(self, issuer_name):
+        if not isinstance(issuer_name, Name):
+            raise TypeError('Expecting x509.Name object.')
+        if self._issuer_name is not None:
+            raise ValueError('The issuer name may only be set once.')
+        return CertificateRevocationListBuilder(
+            issuer_name, self._last_update, self._next_update,
+            self._extensions, self._revoked_certificates
+        )
+
+    def last_update(self, last_update):
+        if not isinstance(last_update, datetime.datetime):
+            raise TypeError('Expecting datetime object.')
+        if self._last_update is not None:
+            raise ValueError('Last update may only be set once.')
+        if last_update <= _UNIX_EPOCH:
+            raise ValueError('The last update date must be after the unix'
+                             ' epoch (1970 January 1).')
+        if self._next_update is not None and last_update > self._next_update:
+            raise ValueError(
+                'The last update date must be before the next update date.'
+            )
+        return CertificateRevocationListBuilder(
+            self._issuer_name, last_update, self._next_update,
+            self._extensions, self._revoked_certificates
+        )
+
+    def next_update(self, next_update):
+        if not isinstance(next_update, datetime.datetime):
+            raise TypeError('Expecting datetime object.')
+        if self._next_update is not None:
+            raise ValueError('Last update may only be set once.')
+        if next_update <= _UNIX_EPOCH:
+            raise ValueError('The last update date must be after the unix'
+                             ' epoch (1970 January 1).')
+        if self._last_update is not None and next_update < self._last_update:
+            raise ValueError(
+                'The next update date must be after the last update date.'
+            )
+        return CertificateRevocationListBuilder(
+            self._issuer_name, self._last_update, next_update,
+            self._extensions, self._revoked_certificates
+        )
+
+    def sign(self, private_key, algorithm, backend):
+        if self._issuer_name is None:
+            raise ValueError("A CRL must have an issuer name")
+
+        if self._last_update is None:
+            raise ValueError("A CRL must have a last update time")
+
+        if self._next_update is None:
+            raise ValueError("A CRL must have a next update time")
+
+        return backend.create_x509_crl(self, private_key, algorithm)
diff --git a/tests/hazmat/backends/test_openssl.py b/tests/hazmat/backends/test_openssl.py
index fd4030f..6c824d2 100644
--- a/tests/hazmat/backends/test_openssl.py
+++ b/tests/hazmat/backends/test_openssl.py
@@ -501,9 +501,12 @@
             backend.create_x509_certificate(object(), private_key, DummyHash())
 
 
-def test_crl_creation_not_implemented():
-    with pytest.raises(NotImplementedError):
-        backend.create_x509_crl("", "", "")
+class TestOpenSSLSignX509CertificateRevocationList(object):
+    def test_invalid_builder(self):
+        private_key = RSA_KEY_2048.private_key(backend)
+
+        with pytest.raises(TypeError):
+            backend.create_x509_crl(object(), private_key, hashes.SHA256())
 
 
 class TestOpenSSLSerialisationWithOpenSSL(object):
diff --git a/tests/test_x509_crlbuilder.py b/tests/test_x509_crlbuilder.py
new file mode 100644
index 0000000..c6b2317
--- /dev/null
+++ b/tests/test_x509_crlbuilder.py
@@ -0,0 +1,222 @@
+# This file is dual licensed under the terms of the Apache License, Version
+# 2.0, and the BSD License. See the LICENSE file in the root of this repository
+# for complete details.
+
+from __future__ import absolute_import, division, print_function
+
+import datetime
+
+import pytest
+
+from cryptography import x509
+from cryptography.hazmat.backends.interfaces import (
+    DSABackend, EllipticCurveBackend, RSABackend, X509Backend
+)
+from cryptography.hazmat.primitives import hashes
+from cryptography.hazmat.primitives.asymmetric import ec
+from cryptography.x509.oid import NameOID
+
+from .hazmat.primitives.fixtures_dsa import DSA_KEY_2048
+from .hazmat.primitives.fixtures_rsa import RSA_KEY_2048, RSA_KEY_512
+from .hazmat.primitives.test_ec import _skip_curve_unsupported
+
+
+class TestCertificateRevocationListBuilder(object):
+    def test_issuer_name_invalid(self):
+        builder = x509.CertificateRevocationListBuilder()
+        with pytest.raises(TypeError):
+            builder.issuer_name("notanx509name")
+
+    def test_set_issuer_name_twice(self):
+        builder = x509.CertificateRevocationListBuilder().issuer_name(
+            x509.Name([x509.NameAttribute(NameOID.COUNTRY_NAME, u'US')])
+        )
+        with pytest.raises(ValueError):
+            builder.issuer_name(
+                x509.Name([x509.NameAttribute(NameOID.COUNTRY_NAME, u'US')])
+            )
+
+    def test_last_update_invalid(self):
+        builder = x509.CertificateRevocationListBuilder()
+        with pytest.raises(TypeError):
+            builder.last_update("notadatetime")
+
+    def test_last_update_before_unix_epoch(self):
+        builder = x509.CertificateRevocationListBuilder()
+        with pytest.raises(ValueError):
+            builder.last_update(datetime.datetime(1960, 8, 10))
+
+    def test_set_last_update_twice(self):
+        builder = x509.CertificateRevocationListBuilder().last_update(
+            datetime.datetime(2002, 1, 1, 12, 1)
+        )
+        with pytest.raises(ValueError):
+            builder.last_update(datetime.datetime(2002, 1, 1, 12, 1))
+
+    def test_next_update_invalid(self):
+        builder = x509.CertificateRevocationListBuilder()
+        with pytest.raises(TypeError):
+            builder.next_update("notadatetime")
+
+    def test_next_update_before_unix_epoch(self):
+        builder = x509.CertificateRevocationListBuilder()
+        with pytest.raises(ValueError):
+            builder.next_update(datetime.datetime(1960, 8, 10))
+
+    def test_set_next_update_twice(self):
+        builder = x509.CertificateRevocationListBuilder().next_update(
+            datetime.datetime(2002, 1, 1, 12, 1)
+        )
+        with pytest.raises(ValueError):
+            builder.next_update(datetime.datetime(2002, 1, 1, 12, 1))
+
+    def test_last_update_after_next_update(self):
+        builder = x509.CertificateRevocationListBuilder()
+
+        builder = builder.next_update(
+            datetime.datetime(2002, 1, 1, 12, 1)
+        )
+        with pytest.raises(ValueError):
+            builder.last_update(datetime.datetime(2003, 1, 1, 12, 1))
+
+    def test_next_update_after_last_update(self):
+        builder = x509.CertificateRevocationListBuilder()
+
+        builder = builder.last_update(
+            datetime.datetime(2002, 1, 1, 12, 1)
+        )
+        with pytest.raises(ValueError):
+            builder.next_update(datetime.datetime(2001, 1, 1, 12, 1))
+
+    @pytest.mark.requires_backend_interface(interface=RSABackend)
+    @pytest.mark.requires_backend_interface(interface=X509Backend)
+    def test_no_issuer_name(self, backend):
+        private_key = RSA_KEY_2048.private_key(backend)
+        builder = x509.CertificateRevocationListBuilder().last_update(
+            datetime.datetime(2002, 1, 1, 12, 1)
+        ).next_update(
+            datetime.datetime(2030, 1, 1, 12, 1)
+        )
+
+        with pytest.raises(ValueError):
+            builder.sign(private_key, hashes.SHA256(), backend)
+
+    @pytest.mark.requires_backend_interface(interface=RSABackend)
+    @pytest.mark.requires_backend_interface(interface=X509Backend)
+    def test_no_last_update(self, backend):
+        private_key = RSA_KEY_2048.private_key(backend)
+        builder = x509.CertificateRevocationListBuilder().issuer_name(
+            x509.Name([x509.NameAttribute(NameOID.COUNTRY_NAME, u'US')])
+        ).next_update(
+            datetime.datetime(2030, 1, 1, 12, 1)
+        )
+
+        with pytest.raises(ValueError):
+            builder.sign(private_key, hashes.SHA256(), backend)
+
+    @pytest.mark.requires_backend_interface(interface=RSABackend)
+    @pytest.mark.requires_backend_interface(interface=X509Backend)
+    def test_no_next_update(self, backend):
+        private_key = RSA_KEY_2048.private_key(backend)
+        builder = x509.CertificateRevocationListBuilder().issuer_name(
+            x509.Name([x509.NameAttribute(NameOID.COUNTRY_NAME, u'US')])
+        ).last_update(
+            datetime.datetime(2030, 1, 1, 12, 1)
+        )
+
+        with pytest.raises(ValueError):
+            builder.sign(private_key, hashes.SHA256(), backend)
+
+    @pytest.mark.requires_backend_interface(interface=RSABackend)
+    @pytest.mark.requires_backend_interface(interface=X509Backend)
+    def test_sign_empty_list(self, backend):
+        private_key = RSA_KEY_2048.private_key(backend)
+        last_update = datetime.datetime(2002, 1, 1, 12, 1)
+        next_update = datetime.datetime(2030, 1, 1, 12, 1)
+        builder = x509.CertificateRevocationListBuilder().issuer_name(
+            x509.Name([
+                x509.NameAttribute(NameOID.COMMON_NAME, u"cryptography.io CA")
+            ])
+        ).last_update(last_update).next_update(next_update)
+
+        crl = builder.sign(private_key, hashes.SHA256(), backend)
+        assert len(crl) == 0
+        assert crl.last_update == last_update
+        assert crl.next_update == next_update
+
+    @pytest.mark.requires_backend_interface(interface=RSABackend)
+    @pytest.mark.requires_backend_interface(interface=X509Backend)
+    def test_sign_rsa_key_too_small(self, backend):
+        private_key = RSA_KEY_512.private_key(backend)
+        last_update = datetime.datetime(2002, 1, 1, 12, 1)
+        next_update = datetime.datetime(2030, 1, 1, 12, 1)
+        builder = x509.CertificateRevocationListBuilder().issuer_name(
+            x509.Name([
+                x509.NameAttribute(NameOID.COMMON_NAME, u"cryptography.io CA")
+            ])
+        ).last_update(
+            last_update
+        ).next_update(
+            next_update
+        )
+
+        with pytest.raises(ValueError):
+            builder.sign(private_key, hashes.SHA512(), backend)
+
+    @pytest.mark.requires_backend_interface(interface=RSABackend)
+    @pytest.mark.requires_backend_interface(interface=X509Backend)
+    def test_sign_with_invalid_hash(self, backend):
+        private_key = RSA_KEY_2048.private_key(backend)
+        last_update = datetime.datetime(2002, 1, 1, 12, 1)
+        next_update = datetime.datetime(2030, 1, 1, 12, 1)
+        builder = x509.CertificateRevocationListBuilder().issuer_name(
+            x509.Name([
+                x509.NameAttribute(NameOID.COMMON_NAME, u"cryptography.io CA")
+            ])
+        ).last_update(
+            last_update
+        ).next_update(
+            next_update
+        )
+
+        with pytest.raises(TypeError):
+            builder.sign(private_key, object(), backend)
+
+    @pytest.mark.requires_backend_interface(interface=DSABackend)
+    @pytest.mark.requires_backend_interface(interface=X509Backend)
+    def test_sign_dsa_key_unsupported(self, backend):
+        private_key = DSA_KEY_2048.private_key(backend)
+        last_update = datetime.datetime(2002, 1, 1, 12, 1)
+        next_update = datetime.datetime(2030, 1, 1, 12, 1)
+        builder = x509.CertificateRevocationListBuilder().issuer_name(
+            x509.Name([
+                x509.NameAttribute(NameOID.COMMON_NAME, u"cryptography.io CA")
+            ])
+        ).last_update(
+            last_update
+        ).next_update(
+            next_update
+        )
+
+        with pytest.raises(NotImplementedError):
+            builder.sign(private_key, hashes.SHA256(), backend)
+
+    @pytest.mark.requires_backend_interface(interface=EllipticCurveBackend)
+    @pytest.mark.requires_backend_interface(interface=X509Backend)
+    def test_sign_ec_key_unsupported(self, backend):
+        _skip_curve_unsupported(backend, ec.SECP256R1())
+        private_key = ec.generate_private_key(ec.SECP256R1(), backend)
+        last_update = datetime.datetime(2002, 1, 1, 12, 1)
+        next_update = datetime.datetime(2030, 1, 1, 12, 1)
+        builder = x509.CertificateRevocationListBuilder().issuer_name(
+            x509.Name([
+                x509.NameAttribute(NameOID.COMMON_NAME, u"cryptography.io CA")
+            ])
+        ).last_update(
+            last_update
+        ).next_update(
+            next_update
+        )
+
+        with pytest.raises(NotImplementedError):
+            builder.sign(private_key, hashes.SHA256(), backend)