diff --git a/lib/actions/holder-actions.js b/lib/actions/holder-actions.js
--- a/lib/actions/holder-actions.js
+++ b/lib/actions/holder-actions.js
@@ -4,6 +4,8 @@
 import * as React from 'react';
 
 import { useInvalidCSATLogOut } from './user-actions.js';
+import type { HolderStoreOperation } from '../ops/holder-store-ops.js';
+import { createReplaceHoldersOperation } from '../ops/holder-store-ops.js';
 import {
   type AuthMetadata,
   IdentityClientContext,
@@ -11,14 +13,17 @@
 import type {
   BlobHashAndHolder,
   BlobOperation,
+  HolderItem,
+  StoredHolders,
 } from '../types/holder-types.js';
-import { holderStatuses } from '../types/holder-types.js';
+import { holderStatuses, shouldHolderExist } from '../types/holder-types.js';
 import { toBase64URL } from '../utils/base64.js';
 import {
   generateBlobHolder,
   assignMultipleHolders,
   removeMultipleHolders,
 } from '../utils/blob-service.js';
+import { getContentSigningKey } from '../utils/crypto-utils.js';
 import { useDispatchActionPromise } from '../utils/redux-promise-utils.js';
 import { useSelector } from '../utils/redux-utils.js';
 import { createDefaultHTTPRequestHeaders } from '../utils/services-utils.js';
@@ -232,4 +237,35 @@
   );
 }
 
-export { processHoldersAction, useClearAllHolders, useProcessBlobHolders };
+async function generateOpsToEstablishHoldersOnDevice(
+  storedHolders: StoredHolders,
+): Promise<$ReadOnlyArray<HolderStoreOperation>> {
+  const deviceID = await getContentSigningKey();
+  const newHolders: Array<HolderItem> = [];
+  const hashesToRemove: Array<string> = [];
+  for (const hash in storedHolders) {
+    const { status } = storedHolders[hash];
+    if (shouldHolderExist(status)) {
+      newHolders.push({
+        hash,
+        holder: generateBlobHolder(deviceID),
+        // This will trigger HoldersHandler, which is responsible for making
+        // sure the holder will be established.
+        status: holderStatuses.NOT_ESTABLISHED,
+      });
+    } else {
+      hashesToRemove.push(hash);
+    }
+  }
+  return [
+    { type: 'remove_holders', payload: { hashes: hashesToRemove } },
+    createReplaceHoldersOperation(newHolders),
+  ];
+}
+
+export {
+  processHoldersAction,
+  useClearAllHolders,
+  useProcessBlobHolders,
+  generateOpsToEstablishHoldersOnDevice,
+};
diff --git a/lib/backup/use-user-data-restore.js b/lib/backup/use-user-data-restore.js
--- a/lib/backup/use-user-data-restore.js
+++ b/lib/backup/use-user-data-restore.js
@@ -6,6 +6,7 @@
 import { runRestoredBackupMigrations } from './restored-migrations.js';
 import { restoreUserDataStepActionTypes } from '../actions/backup-actions.js';
 import { setClientDBStoreActionType } from '../actions/client-db-store-actions.js';
+import { generateOpsToEstablishHoldersOnDevice } from '../actions/holder-actions.js';
 import { logTypes, useDebugLogs } from '../components/debug-logs-context.js';
 import {
   restoreUserDataSteps,
@@ -40,6 +41,7 @@
         restoreUserDataSteps.RESTORE_DATABASE,
         restoreUserDataSteps.MIGRATE_BACKUP_SCHEMA,
         restoreUserDataSteps.RUN_RESTORED_BACKUP_MIGRATIONS,
+        restoreUserDataSteps.ASSIGN_NEW_HOLDERS,
         restoreUserDataSteps.COPY_CONTENT_FROM_BACKUP_DB,
       ];
       let startStepIndex = 0;
@@ -57,7 +59,7 @@
       }
 
       // if all steps from last restore succeeded, start from scratch
-      if (startStepIndex > 3) {
+      if (startStepIndex > 4) {
         startStepIndex = 0;
       }
 
@@ -181,8 +183,32 @@
         await runRestoredMigrationsPromise;
       }
 
-      // 4. Copy content to main database
+      // 4. Assign holders for the new device
       if (startStepIndex <= 3) {
+        const assignHoldersPromise = (async () => {
+          const holders = await sqliteAPI.getHolders(
+            databaseIdentifier.RESTORED,
+          );
+          const holderStoreOperations =
+            await generateOpsToEstablishHoldersOnDevice(holders);
+          await sqliteAPI.processDBStoreOperations(
+            {
+              holderStoreOperations,
+            },
+            databaseIdentifier.RESTORED,
+          );
+        })();
+        void dispatchActionPromise(
+          restoreUserDataStepActionTypes,
+          assignHoldersPromise,
+          undefined,
+          { step: 'assign_new_holders' },
+        );
+        await assignHoldersPromise;
+      }
+
+      // 5. Copy content to main database
+      if (startStepIndex <= 4) {
         const copyContentPromise = sqliteAPI.copyContentFromBackupDatabase();
         void dispatchActionPromise(
           restoreUserDataStepActionTypes,
@@ -193,7 +219,7 @@
         await copyContentPromise;
       }
 
-      // 5. Populate store
+      // 6. Populate store
       const clientDBStore = await sqliteAPI.getClientDBStore(
         databaseIdentifier.MAIN,
         identityAuthResult.userID,
diff --git a/lib/reducers/backup-reducer.js b/lib/reducers/backup-reducer.js
--- a/lib/reducers/backup-reducer.js
+++ b/lib/reducers/backup-reducer.js
@@ -142,6 +142,7 @@
   restoreUserDataSteps.RESTORE_DATABASE,
   restoreUserDataSteps.MIGRATE_BACKUP_SCHEMA,
   restoreUserDataSteps.RUN_RESTORED_BACKUP_MIGRATIONS,
+  restoreUserDataSteps.ASSIGN_NEW_HOLDERS,
   restoreUserDataSteps.COPY_CONTENT_FROM_BACKUP_DB,
 ];
 function validateUserDataRestoreStepOrder(
diff --git a/lib/types/backup-types.js b/lib/types/backup-types.js
--- a/lib/types/backup-types.js
+++ b/lib/types/backup-types.js
@@ -86,6 +86,7 @@
   RESTORE_DATABASE: 'restore_database',
   MIGRATE_BACKUP_SCHEMA: 'migrate_backup_schema',
   RUN_RESTORED_BACKUP_MIGRATIONS: 'run_restored_backup_migrations',
+  ASSIGN_NEW_HOLDERS: 'assign_new_holders',
   COPY_CONTENT_FROM_BACKUP_DB: 'copy_content_from_backup_db',
 });
 export type RestoreUserDataStep = $Values<typeof restoreUserDataSteps>;
diff --git a/lib/types/holder-types.js b/lib/types/holder-types.js
--- a/lib/types/holder-types.js
+++ b/lib/types/holder-types.js
@@ -23,6 +23,14 @@
   return holderStatus;
 }
 
+export function shouldHolderExist(holderStatus: HolderStatus): boolean {
+  return (
+    holderStatus === holderStatuses.PENDING_ESTABLISHMENT ||
+    holderStatus === holderStatuses.ESTABLISHED ||
+    holderStatus === holderStatuses.NOT_ESTABLISHED
+  );
+}
+
 export type HolderInfo = {
   +holder: string,
   +status: HolderStatus,