diff --git a/services/identity/src/client_service.rs b/services/identity/src/client_service.rs
--- a/services/identity/src/client_service.rs
+++ b/services/identity/src/client_service.rs
@@ -474,9 +474,33 @@
 
   async fn delete_user(
     &self,
-    _request: tonic::Request<DeleteUserRequest>,
+    request: tonic::Request<DeleteUserRequest>,
   ) -> Result<tonic::Response<Empty>, tonic::Status> {
-    unimplemented!();
+    let message = request.into_inner();
+
+    let access_token = self
+      .client
+      .get_access_token_data(message.user_id.clone(), message.device_id_key)
+      .await
+      .map_err(handle_db_error)?;
+
+    if let Some(token) = access_token {
+      if !token.is_valid() || token.access_token != message.access_token {
+        return Err(tonic::Status::permission_denied("bad token"));
+      }
+
+      self
+        .client
+        .delete_user(message.user_id)
+        .await
+        .map_err(handle_db_error)?;
+
+      let response = Empty {};
+
+      Ok(Response::new(response))
+    } else {
+      Err(tonic::Status::permission_denied("bad token"))
+    }
   }
 
   async fn generate_nonce(
diff --git a/services/identity/src/token.rs b/services/identity/src/token.rs
--- a/services/identity/src/token.rs
+++ b/services/identity/src/token.rs
@@ -38,4 +38,8 @@
       valid: true,
     }
   }
+
+  pub fn is_valid(&self) -> bool {
+    self.valid
+  }
 }
diff --git a/shared/protos/identity_client.proto b/shared/protos/identity_client.proto
--- a/shared/protos/identity_client.proto
+++ b/shared/protos/identity_client.proto
@@ -219,6 +219,10 @@
 
 message DeleteUserRequest {
   string accessToken = 1;
+  string userID = 2;
+  // Public ed25519 key used for signing. We need this to look up a device's
+  // access token
+  string deviceIDKey = 3;
 }
 
 // GenerateNonce