diff --git a/cryptography/exceptions.py b/cryptography/exceptions.py
index d7c867d..88766cc 100644
--- a/cryptography/exceptions.py
+++ b/cryptography/exceptions.py
@@ -60,3 +60,7 @@
 
 class InvalidToken(Exception):
     pass
+
+
+class UnsupportedInterface(Exception):
+    pass
diff --git a/cryptography/hazmat/primitives/twofactor/hotp.py b/cryptography/hazmat/primitives/twofactor/hotp.py
index 8326022..27476fd 100644
--- a/cryptography/hazmat/primitives/twofactor/hotp.py
+++ b/cryptography/hazmat/primitives/twofactor/hotp.py
@@ -17,13 +17,19 @@
 
 import six
 
-from cryptography.exceptions import InvalidToken
+from cryptography.exceptions import InvalidToken, UnsupportedInterface
+from cryptography.hazmat.backends.interfaces import HMACBackend
 from cryptography.hazmat.primitives import constant_time, hmac
 from cryptography.hazmat.primitives.hashes import SHA1, SHA256, SHA512
 
 
 class HOTP(object):
     def __init__(self, key, length, algorithm, backend):
+
+        if not isinstance(backend, HMACBackend):
+            raise UnsupportedInterface(
+                "Backend object does not implement HMACBackend")
+
         if len(key) < 16:
             raise ValueError("Key length has to be at least 128 bits.")
 
diff --git a/cryptography/hazmat/primitives/twofactor/totp.py b/cryptography/hazmat/primitives/twofactor/totp.py
index 0630de6..0ce3ada 100644
--- a/cryptography/hazmat/primitives/twofactor/totp.py
+++ b/cryptography/hazmat/primitives/twofactor/totp.py
@@ -13,13 +13,19 @@
 
 from __future__ import absolute_import, division, print_function
 
-from cryptography.exceptions import InvalidToken
+from cryptography.exceptions import InvalidToken, UnsupportedInterface
+from cryptography.hazmat.backends.interfaces import HMACBackend
 from cryptography.hazmat.primitives import constant_time
 from cryptography.hazmat.primitives.twofactor.hotp import HOTP
 
 
 class TOTP(object):
     def __init__(self, key, length, algorithm, time_step, backend):
+
+        if not isinstance(backend, HMACBackend):
+            raise UnsupportedInterface(
+                "Backend object does not implement HMACBackend")
+
         self._time_step = time_step
         self._hotp = HOTP(key, length, algorithm, backend)
 
diff --git a/docs/exceptions.rst b/docs/exceptions.rst
index 48c4bca..e5010eb 100644
--- a/docs/exceptions.rst
+++ b/docs/exceptions.rst
@@ -56,3 +56,9 @@
     This is raised when the verify method of a one time password function's
     computed token does not match the expected token.
 
+.. class:: UnsupportedInterface
+
+    .. versionadded:: 0.3
+
+    This is raised when the provided backend does not support the required
+    interface.
diff --git a/docs/hazmat/primitives/twofactor.rst b/docs/hazmat/primitives/twofactor.rst
index 3912d48..124d0ef 100644
--- a/docs/hazmat/primitives/twofactor.rst
+++ b/docs/hazmat/primitives/twofactor.rst
@@ -52,6 +52,9 @@
         :class:`~cryptography.hazmat.primitives.hashes.SHA256()` or
         :class:`~cryptography.hazmat.primitives.hashes.SHA512()` or if the
         ``length`` parameter is not an integer.
+    :raises cryptography.exceptions.UnsupportedInterface: This is raised if the
+        provided ``backend`` does not implement
+        :class:`~cryptography.hazmat.backends.interfaces.HMACBackend`
 
     .. method:: generate(counter)
 
@@ -148,6 +151,9 @@
         :class:`~cryptography.hazmat.primitives.hashes.SHA256()` or
         :class:`~cryptography.hazmat.primitives.hashes.SHA512()` or if the
         ``length`` parameter is not an integer.
+    :raises cryptography.exceptions.UnsupportedInterface: This is raised if the
+        provided ``backend`` does not implement
+        :class:`~cryptography.hazmat.backends.interfaces.HMACBackend`
 
     .. method:: generate(time)
 
diff --git a/tests/hazmat/primitives/twofactor/test_hotp.py b/tests/hazmat/primitives/twofactor/test_hotp.py
index bc907c9..0ef1897 100644
--- a/tests/hazmat/primitives/twofactor/test_hotp.py
+++ b/tests/hazmat/primitives/twofactor/test_hotp.py
@@ -15,9 +15,11 @@
 
 import os
 
+import pretend
+
 import pytest
 
-from cryptography.exceptions import InvalidToken
+from cryptography.exceptions import InvalidToken, UnsupportedInterface
 from cryptography.hazmat.primitives.twofactor.hotp import HOTP
 from cryptography.hazmat.primitives import hashes
 from tests.utils import load_vectors_from_file, load_nist_vectors
@@ -95,3 +97,12 @@
 
         with pytest.raises(TypeError):
             HOTP(secret, b"foo", SHA1(), backend)
+
+
+def test_invalid_backend():
+    secret = b"12345678901234567890"
+
+    pretend_backend = pretend.stub()
+
+    with pytest.raises(UnsupportedInterface):
+        HOTP(secret, 8, hashes.SHA1(), pretend_backend)
diff --git a/tests/hazmat/primitives/twofactor/test_totp.py b/tests/hazmat/primitives/twofactor/test_totp.py
index f3bddb8..776a9f2 100644
--- a/tests/hazmat/primitives/twofactor/test_totp.py
+++ b/tests/hazmat/primitives/twofactor/test_totp.py
@@ -13,9 +13,11 @@
 
 from __future__ import absolute_import, division, print_function
 
+import pretend
+
 import pytest
 
-from cryptography.exceptions import InvalidToken
+from cryptography.exceptions import InvalidToken, UnsupportedInterface
 from cryptography.hazmat.primitives import hashes
 from cryptography.hazmat.primitives.twofactor.totp import TOTP
 from tests.utils import load_vectors_from_file, load_nist_vectors
@@ -129,3 +131,12 @@
         totp = TOTP(secret, 8, hashes.SHA1(), 30, backend)
 
         assert totp.generate(time) == b"94287082"
+
+
+def test_invalid_backend():
+    secret = b"12345678901234567890"
+
+    pretend_backend = pretend.stub()
+
+    with pytest.raises(UnsupportedInterface):
+        TOTP(secret, 8, hashes.SHA1(), 30, pretend_backend)