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
@@ -140,10 +140,16 @@
   const orderedMessageInfos = sortMessageInfoList(unshimmed);
   const messages = _keyBy(messageID)(orderedMessageInfos);
 
-  const messageStoreOperations = orderedMessageInfos.map(messageInfo => ({
-    type: 'replace',
-    payload: { id: messageID(messageInfo), messageInfo },
-  }));
+  const messageStoreReplaceOperations = orderedMessageInfos.map(
+    messageInfo => ({
+      type: 'replace',
+      payload: { id: messageID(messageInfo), messageInfo },
+    }),
+  );
+  const messageStoreOperations = [
+    { type: 'remove_all' },
+    ...messageStoreReplaceOperations,
+  ];
 
   const threadsToMessageIDs = mapThreadsToMessageIDsFromOrderedMessageInfos(
     orderedMessageInfos,