diff --git a/native/account/qr-auth/primary-device-qr-auth-context-provider.js b/native/account/qr-auth/primary-device-qr-auth-context-provider.js
--- a/native/account/qr-auth/primary-device-qr-auth-context-provider.js
+++ b/native/account/qr-auth/primary-device-qr-auth-context-provider.js
@@ -136,6 +136,7 @@
   }, [addListener, removeListener, tunnelbrokerMessageListener]);
 
   const processDeviceListUpdate = React.useCallback(async () => {
+    let deviceListHasBeenUpdated = false;
     try {
       const { deviceID: primaryDeviceID, userID } =
         await identityContext.getAuthMetadata();
@@ -173,6 +174,7 @@
       };
 
       const handleReplaceDevice = async () => {
+        let keyserverHasBeenReplaced = false;
         try {
           if (!keyserverDeviceID) {
             throw new Error('missing keyserver device ID');
@@ -182,6 +184,7 @@
             deviceIDToRemove: keyserverDeviceID,
             newDeviceID: targetDeviceID,
           });
+          keyserverHasBeenReplaced = true;
           await sendDeviceListUpdateSuccessMessage();
         } catch (err) {
           addLog(
@@ -189,6 +192,12 @@
               ` with ${targetDeviceID}: `,
             getMessageForException(err) ?? 'unknown error',
           );
+          if (keyserverHasBeenReplaced) {
+            void runDeviceListUpdate({
+              type: 'remove',
+              deviceID: targetDeviceID,
+            });
+          }
 
           Alert.alert(
             'Adding device failed',
@@ -208,6 +217,7 @@
           type: 'add',
           deviceID: targetDeviceID,
         });
+        deviceListHasBeenUpdated = true;
         await sendDeviceListUpdateSuccessMessage();
         return;
       }
@@ -236,6 +246,12 @@
         `Error adding device ${targetDeviceID ?? ''}`,
         getMessageForException(err) ?? 'unknown error',
       );
+      if (targetDeviceID && deviceListHasBeenUpdated) {
+        void runDeviceListUpdate({
+          type: 'remove',
+          deviceID: targetDeviceID,
+        });
+      }
 
       Alert.alert('Adding device failed', 'Failed to update the device list', [
         { text: 'OK' },