diff --git a/keystone/identity/core.py b/keystone/identity/core.py
index e029743..e6f63aa 100644
--- a/keystone/identity/core.py
+++ b/keystone/identity/core.py
@@ -508,6 +508,14 @@ class UserController(wsgi.Application):
     def delete_user(self, context, user_id):
         self.assert_admin(context)
         self.identity_api.delete_user(context, user_id)
+        try:
+            for token_id in self.token_api.list_tokens(context, user_id):
+                self.token_api.delete_token(context, token_id)
+        except exception.NotImplemented:
+            # The users status has been changed but tokens remain valid for
+            # backends that can't list tokens for users
+            LOG.warning('User %s status has changed, but existing tokens '
+                        'remain valid' % user_id)
 
     def set_user_enabled(self, context, user_id, user):
         return self.update_user(context, user_id, user)
diff --git a/tests/test_keystoneclient.py b/tests/test_keystoneclient.py
index a45e27b..e65c7ef 100644
--- a/tests/test_keystoneclient.py
+++ b/tests/test_keystoneclient.py
@@ -385,6 +385,30 @@ class KeystoneClientTests(object):
                           self.get_client,
                           self.user_foo)
 
+    def test_delete_user_invalidates_token(self):
+        from keystoneclient import exceptions as client_exceptions
+
+        admin_client = self.get_client(admin=True)
+        client = self.get_client(admin=False)
+
+        username = uuid.uuid4().hex
+        password = uuid.uuid4().hex
+        user_id = admin_client.users.create(
+            name=username, password=password, email=uuid.uuid4().hex).id
+
+        token_id = client.tokens.authenticate(
+            username=username, password=password).id
+
+        # token should be usable before the user is deleted
+        client.tokens.authenticate(token=token_id)
+
+        admin_client.users.delete(user=user_id)
+
+        # authenticate with a token should not work after the user is deleted
+        self.assertRaises(client_exceptions.Unauthorized,
+                          client.tokens.authenticate,
+                          token=token_id)
+
     def test_token_expiry_maintained(self):
         foo_client = self.get_client(self.user_foo)
         orig_token = foo_client.service_catalog.catalog['token']