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
@@ -1285,24 +1285,33 @@
       },
     };
   } else if (action.type === setMessageStoreMessages) {
-    // When starting the app on native, we filter out any local-only multimedia
-    // messages because the relevant context is no longer available
     let threads = { ...messageStore.threads };
     let local = { ...messageStore.local };
 
+    // Store message IDs already contained within threads so that we
+    // do not insert duplicates
+    const existingMessageIDs = new Set();
+    for (const threadID in threads) {
+      threads[threadID].messageIDs.forEach(msgID => {
+        existingMessageIDs.add(msgID);
+      });
+    }
+    const threadsNeedMsgIDsResorting = new Set();
     const actionPayloadMessages = translateClientDBMessageInfosToRawMessageInfos(
       action.payload,
     );
-    const messageIDsToBeRemoved = [];
 
+    // When starting the app on native, we filter out any local-only multimedia
+    // messages because the relevant context is no longer available
+    const messageIDsToBeRemoved = [];
     for (const id in actionPayloadMessages) {
       const message = actionPayloadMessages[id];
+      const { threadID } = message;
       if (
         (message.type === messageTypes.IMAGES ||
           message.type === messageTypes.MULTIMEDIA) &&
         !message.id
       ) {
-        const { threadID } = message;
         messageIDsToBeRemoved.push(id);
         threads = {
           ...threads,
@@ -1316,9 +1325,24 @@
         local = _pickBy(
           (localInfo: LocalMessageInfo, key: string) => key !== id,
         )(local);
+      } else if (!existingMessageIDs.has(id)) {
+        threads = {
+          ...threads,
+          [threadID]: {
+            ...threads[threadID],
+            messageIDs: [...threads[threadID].messageIDs, id],
+          },
+        };
+        threadsNeedMsgIDsResorting.add(threadID);
       }
     }
 
+    for (const threadID of threadsNeedMsgIDsResorting) {
+      threads[threadID].messageIDs = sortMessageIDs(actionPayloadMessages)(
+        threads[threadID].messageIDs,
+      );
+    }
+
     messageStore = {
       ...messageStore,
       messages: actionPayloadMessages,