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
@@ -738,6 +738,9 @@
     user_id: String,
     device_id_key: String,
   ) -> Result<(), Error> {
+    // delete from new device list too
+    self.remove_device(&user_id, &device_id_key).await?;
+
     let update_expression =
       format!("REMOVE {}.{}", USERS_TABLE_DEVICES_ATTRIBUTE, "#deviceID");
 
diff --git a/services/identity/src/database/device_list.rs b/services/identity/src/database/device_list.rs
--- a/services/identity/src/database/device_list.rs
+++ b/services/identity/src/database/device_list.rs
@@ -5,8 +5,8 @@
   aws::ddb::{
     operation::{get_item::GetItemOutput, query::builders::QueryFluentBuilder},
     types::{
-      error::TransactionCanceledException, AttributeValue, DeleteRequest, Put,
-      TransactWriteItem, Update, WriteRequest,
+      error::TransactionCanceledException, AttributeValue, Delete,
+      DeleteRequest, Put, TransactWriteItem, Update, WriteRequest,
     },
   },
   database::{
@@ -651,6 +651,51 @@
       .await
   }
 
+  /// Removes device from user's device list. If the device doesn't exist, the
+  /// operation fails. Transactionally generates new device list version.
+  pub async fn remove_device(
+    &self,
+    user_id: impl Into<String>,
+    device_id: impl AsRef<str>,
+  ) -> Result<(), Error> {
+    let user_id: String = user_id.into();
+    let device_id = device_id.as_ref();
+    self
+      .transact_update_devicelist(&user_id, |ref mut device_ids| {
+        let device_exists = device_ids.iter().any(|id| id == device_id);
+        if !device_exists {
+          warn!(
+            "Device doesn't exist in user's device list \
+          (userID={}, deviceID={})",
+            &user_id, device_id
+          );
+          return Err(Error::DeviceList(DeviceListError::DeviceNotFound));
+        }
+
+        device_ids.retain(|id| id != device_id);
+
+        // Delete device DDB operation
+        let delete_device = Delete::builder()
+          .table_name(devices_table::NAME)
+          .key(ATTR_USER_ID, AttributeValue::S(user_id.clone()))
+          .key(
+            ATTR_ITEM_ID,
+            DeviceIDAttribute(device_id.to_string()).into(),
+          )
+          .condition_expression(
+            "attribute_exists(#user_id) AND attribute_exists(#item_id)",
+          )
+          .expression_attribute_names("#user_id", ATTR_USER_ID)
+          .expression_attribute_names("#item_id", ATTR_ITEM_ID)
+          .build();
+        let operation =
+          TransactWriteItem::builder().delete(delete_device).build();
+
+        Ok(operation)
+      })
+      .await
+  }
+
   /// Performs a transactional update of the device list for the user. Afterwards
   /// generates a new device list and updates the timestamp in the users table.
   /// This is done in a transaction. Operation fails if the device list has been
diff --git a/services/identity/src/error.rs b/services/identity/src/error.rs
--- a/services/identity/src/error.rs
+++ b/services/identity/src/error.rs
@@ -28,6 +28,7 @@
 #[derive(Debug, derive_more::Display, derive_more::Error)]
 pub enum DeviceListError {
   DeviceAlreadyExists,
+  DeviceNotFound,
   ConcurrentUpdateError,
 }