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
@@ -4,6 +4,7 @@
 
 import { runRestoredBackupMigrations } from './restored-migrations.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 { databaseIdentifier } from '../types/database-identifier-types.js';
 import type { IdentityAuthResult } from '../types/identity-service-types.js';
@@ -109,10 +110,21 @@
         throw new Error('backup_is_newer');
       }
 
-      // 4. Copy content to main database
+      // 4. Assign holders for the new device
+      const holders = await sqliteAPI.getHolders(databaseIdentifier.RESTORED);
+      const holderStoreOperations =
+        await generateOpsToEstablishHoldersOnDevice(holders);
+      await sqliteAPI.processDBStoreOperations(
+        {
+          holderStoreOperations,
+        },
+        databaseIdentifier.RESTORED,
+      );
+
+      // 5. Copy content to main database
       await sqliteAPI.copyContentFromBackupDatabase();
 
-      // 5. Populate store
+      // 6. Populate store
       const clientDBStore = await sqliteAPI.getClientDBStore(
         databaseIdentifier.MAIN,
         identityAuthResult.userID,
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,