diff --git a/services/identity/src/database.rs b/services/identity/src/database.rs
--- a/services/identity/src/database.rs
+++ b/services/identity/src/database.rs
@@ -448,6 +448,11 @@
     &self,
     user_id: String,
   ) -> Result<DeleteItemOutput, Error> {
+    // We must delete the one-time keys first because doing so requires device
+    // IDs from the devices table
+    debug!(user_id, "Attempting to delete user's one-time keys");
+    self.delete_otks_table_rows_for_user(&user_id).await?;
+
     debug!(user_id, "Attempting to delete user's devices");
     self.delete_devices_table_rows_for_user(&user_id).await?;
 
diff --git a/services/identity/src/database/one_time_keys.rs b/services/identity/src/database/one_time_keys.rs
--- a/services/identity/src/database/one_time_keys.rs
+++ b/services/identity/src/database/one_time_keys.rs
@@ -417,6 +417,26 @@
 
     Ok(())
   }
+
+  /// Deletes all data for a user from one-time keys table
+  pub async fn delete_otks_table_rows_for_user(
+    &self,
+    user_id: &str,
+  ) -> Result<(), Error> {
+    let maybe_device_list_row = self.get_current_device_list(user_id).await?;
+    let Some(device_list_row) = maybe_device_list_row else {
+      info!("No devices associated with user. Skipping one-time key removal.");
+      return Ok(());
+    };
+
+    for device_id in device_list_row.device_ids {
+      self
+        .delete_otks_table_rows_for_user_device(user_id, &device_id)
+        .await?;
+    }
+
+    Ok(())
+  }
 }
 
 pub struct OTKRow {