diff --git a/lib/reducers/message-reducer.js b/lib/reducers/message-reducer.js
--- a/lib/reducers/message-reducer.js
+++ b/lib/reducers/message-reducer.js
@@ -655,6 +655,7 @@
     return messageStore;
   }
   let processedMessages = { ...messageStore.messages };
+  let processedThreads = { ...messageStore.threads };
   for (const operation of messageStoreOperations) {
     if (operation.type === 'replace') {
       processedMessages[operation.payload.id] = operation.payload.messageInfo;
@@ -678,9 +679,23 @@
       delete processedMessages[operation.payload.from];
     } else if (operation.type === 'remove_all') {
       processedMessages = {};
+    } else if (operation.type === 'replace_threads') {
+      for (const threadID in operation.payload.threads) {
+        processedThreads[threadID] = operation.payload.threads[threadID];
+      }
+    } else if (operation.type === 'remove_threads') {
+      for (const id of operation.payload.ids) {
+        delete processedThreads[id];
+      }
+    } else if (operation.type === 'remove_all_threads') {
+      processedThreads = {};
     }
   }
-  return { ...messageStore, messages: processedMessages };
+  return {
+    ...messageStore,
+    threads: processedThreads,
+    messages: processedMessages,
+  };
 }
 
 type ReduceMessageStoreResult = {
diff --git a/lib/types/message-types.js b/lib/types/message-types.js
--- a/lib/types/message-types.js
+++ b/lib/types/message-types.js
@@ -374,13 +374,18 @@
   +sendFailed?: boolean,
 };
 
+export type MessageStoreThreads = {
+  +[threadID: string]: ThreadMessageInfo,
+};
+
 export type MessageStore = {
   +messages: { +[id: string]: RawMessageInfo },
-  +threads: { +[threadID: string]: ThreadMessageInfo },
+  +threads: MessageStoreThreads,
   +local: { +[id: string]: LocalMessageInfo },
   +currentAsOf: number,
 };
 
+// MessageStore messages ops
 export type RemoveMessageOperation = {
   +type: 'remove',
   +payload: { +ids: $ReadOnlyArray<string> },
@@ -405,6 +410,21 @@
   +type: 'remove_all',
 };
 
+// MessageStore threads ops
+export type ReplaceMessageStoreThreadsOperation = {
+  +type: 'replace_threads',
+  +payload: { +threads: MessageStoreThreads },
+};
+
+export type RemoveMessageStoreThreadsOperation = {
+  +type: 'remove_threads',
+  +payload: { +ids: $ReadOnlyArray<string> },
+};
+
+export type RemoveMessageStoreAllThreadsOperation = {
+  +type: 'remove_all_threads',
+};
+
 // We were initially using `number`s` for `thread`, `type`, `future_type`, etc.
 // However, we ended up changing `thread` to `string` to account for thread IDs
 // including information about the keyserver (eg 'GENESIS|123') in the future.
@@ -437,7 +457,10 @@
   | ReplaceMessageOperation
   | RekeyMessageOperation
   | RemoveMessagesForThreadsOperation
-  | RemoveAllMessagesOperation;
+  | RemoveAllMessagesOperation
+  | ReplaceMessageStoreThreadsOperation
+  | RemoveMessageStoreThreadsOperation
+  | RemoveMessageStoreAllThreadsOperation;
 
 export type ClientDBMessageStoreOperation =
   | RemoveMessageOperation
diff --git a/lib/utils/message-ops-utils.js b/lib/utils/message-ops-utils.js
--- a/lib/utils/message-ops-utils.js
+++ b/lib/utils/message-ops-utils.js
@@ -231,17 +231,27 @@
 function convertMessageStoreOperationsToClientDBOperations(
   messageStoreOperations: $ReadOnlyArray<MessageStoreOperation>,
 ): $ReadOnlyArray<ClientDBMessageStoreOperation> {
-  return messageStoreOperations.map(messageStoreOperation => {
-    if (messageStoreOperation.type !== 'replace') {
-      return messageStoreOperation;
-    }
-    return {
-      type: 'replace',
-      payload: translateRawMessageInfoToClientDBMessageInfo(
-        messageStoreOperation.payload.messageInfo,
-      ),
-    };
-  });
+  const convertedOperations = messageStoreOperations.map(
+    messageStoreOperation => {
+      if (
+        messageStoreOperation.type === 'replace_threads' ||
+        messageStoreOperation.type === 'remove_threads' ||
+        messageStoreOperation.type === 'remove_all_threads'
+      ) {
+        return undefined;
+      }
+      if (messageStoreOperation.type !== 'replace') {
+        return messageStoreOperation;
+      }
+      return {
+        type: 'replace',
+        payload: translateRawMessageInfoToClientDBMessageInfo(
+          messageStoreOperation.payload.messageInfo,
+        ),
+      };
+    },
+  );
+  return convertedOperations.filter(Boolean);
 }
 
 function getPinnedContentFromClientDBMessageInfo(