diff --git a/keyserver/src/push/crypto.js b/keyserver/src/push/crypto.js
--- a/keyserver/src/push/crypto.js
+++ b/keyserver/src/push/crypto.js
@@ -27,6 +27,7 @@
   +notification: apn.Notification,
   +payloadSizeExceeded: boolean,
   +encryptedPayloadHash?: string,
+  +encryptionOrder?: number,
 }> {
   invariant(
     !notification.collapseId,
@@ -63,6 +64,7 @@
     const {
       encryptedMessages: { serializedPayload },
       dbPersistConditionViolated,
+      encryptionOrder,
     } = await encryptAndUpdateOlmSession(
       cookieID,
       'notifications',
@@ -86,6 +88,7 @@
       notification: encryptedNotification,
       payloadSizeExceeded: !!dbPersistConditionViolated,
       encryptedPayloadHash,
+      encryptionOrder,
     };
   } catch (e) {
     console.log('Notification encryption failed: ' + e);
@@ -119,6 +122,7 @@
 ): Promise<{
   +resultPayload: T | { +encryptedPayload: string },
   +payloadSizeExceeded: boolean,
+  +encryptionOrder?: number,
 }> {
   try {
     const unencryptedSerializedPayload = JSON.stringify(unencryptedPayload);
@@ -140,6 +144,7 @@
     const {
       encryptedMessages: { serializedPayload },
       dbPersistConditionViolated,
+      encryptionOrder,
     } = await encryptAndUpdateOlmSession(
       cookieID,
       'notifications',
@@ -151,6 +156,7 @@
     return {
       resultPayload: { encryptedPayload: serializedPayload.body },
       payloadSizeExceeded: !!dbPersistConditionViolated,
+      encryptionOrder,
     };
   } catch (e) {
     console.log('Notification encryption failed: ' + e);
@@ -174,6 +180,7 @@
 ): Promise<{
   +notification: AndroidNotification,
   +payloadSizeExceeded: boolean,
+  +encryptionOrder?: number,
 }> {
   const { id, badgeOnly, ...unencryptedPayload } = notification.data;
   let payloadSizeValidator;
@@ -184,7 +191,7 @@
       return notificationSizeValidator({ data: { id, badgeOnly, ...payload } });
     };
   }
-  const { resultPayload, payloadSizeExceeded } =
+  const { resultPayload, payloadSizeExceeded, encryptionOrder } =
     await encryptAndroidNotificationPayload(
       cookieID,
       unencryptedPayload,
@@ -199,6 +206,7 @@
       },
     },
     payloadSizeExceeded,
+    encryptionOrder,
   };
 }
 
@@ -221,24 +229,30 @@
 async function encryptWebNotification(
   cookieID: string,
   notification: PlainTextWebNotification,
-): Promise<WebNotification> {
+): Promise<{ +notification: WebNotification, +encryptionOrder?: number }> {
   const { id, ...payloadSansId } = notification;
   const unencryptedSerializedPayload = JSON.stringify(payloadSansId);
 
   try {
     const {
       encryptedMessages: { serializedPayload },
+      encryptionOrder,
     } = await encryptAndUpdateOlmSession(cookieID, 'notifications', {
       serializedPayload: unencryptedSerializedPayload,
     });
 
-    return { id, encryptedPayload: serializedPayload.body };
+    return {
+      notification: { id, encryptedPayload: serializedPayload.body },
+      encryptionOrder,
+    };
   } catch (e) {
     console.log('Notification encryption failed: ' + e);
     return {
-      id,
-      encryptionFailed: '1',
-      ...payloadSansId,
+      notification: {
+        id,
+        encryptionFailed: '1',
+        ...payloadSansId,
+      },
     };
   }
 }
@@ -255,6 +269,7 @@
     +notification: apn.Notification,
     +payloadSizeExceeded: boolean,
     +encryptedPayloadHash?: string,
+    +encryptionOrder?: number,
   }>,
 > {
   const notificationPromises = devices.map(
@@ -305,6 +320,7 @@
     +deviceToken: string,
     +notification: AndroidNotification,
     +payloadSizeExceeded: boolean,
+    +encryptionOrder?: number,
   }>,
 > {
   const notificationPromises = devices.map(
@@ -328,6 +344,7 @@
     +cookieID: string,
     +deviceToken: string,
     +notification: AndroidNotificationRescind,
+    +encryptionOrder?: number,
   }>,
 > {
   const notificationPromises = devices.map(
@@ -349,12 +366,13 @@
   $ReadOnlyArray<{
     +deviceToken: string,
     +notification: WebNotification,
+    +encryptionOrder?: number,
   }>,
 > {
   const notificationPromises = devices.map(
     async ({ deviceToken, cookieID }) => {
       const notif = await encryptWebNotification(cookieID, notification);
-      return { notification: notif, deviceToken };
+      return { ...notif, deviceToken };
     },
   );
   return Promise.all(notificationPromises);
diff --git a/keyserver/src/push/rescind.js b/keyserver/src/push/rescind.js
--- a/keyserver/src/push/rescind.js
+++ b/keyserver/src/push/rescind.js
@@ -253,6 +253,7 @@
       +notification: T,
       +cookieID: string,
       +deviceToken: string,
+      +encryptionOrder?: number,
     }>,
   >,
 ): Promise<$ReadOnlyArray<{ +deviceToken: string, +notification: T }>> {
diff --git a/keyserver/src/push/types.js b/keyserver/src/push/types.js
--- a/keyserver/src/push/types.js
+++ b/keyserver/src/push/types.js
@@ -8,6 +8,7 @@
   +notification: apn.Notification,
   +deviceToken: string,
   +encryptedPayloadHash?: string,
+  +encryptionOrder?: number,
 };
 
 type AndroidNotificationPayloadBase = {
@@ -55,11 +56,13 @@
 export type TargetedAndroidNotification = {
   +notification: AndroidNotification | AndroidNotificationRescind,
   +deviceToken: string,
+  +encryptionOrder?: number,
 };
 
 export type TargetedWebNotification = {
   +notification: WebNotification,
   +deviceToken: string,
+  +encryptionOrder?: number,
 };
 
 export type NotificationTargetDevice = {
diff --git a/keyserver/src/updaters/olm-session-updater.js b/keyserver/src/updaters/olm-session-updater.js
--- a/keyserver/src/updaters/olm-session-updater.js
+++ b/keyserver/src/updaters/olm-session-updater.js
@@ -15,6 +15,7 @@
 type OlmEncryptionResult = {
   +encryptedMessages: { +[string]: EncryptResult },
   +dbPersistConditionViolated?: boolean,
+  +encryptionOrder?: number,
 };
 
 async function encryptAndUpdateOlmSession(
@@ -86,7 +87,7 @@
     const [{ versionOnUpdateAttempt }] = selectResult;
 
     if (version === versionOnUpdateAttempt) {
-      return { encryptedMessages };
+      return { encryptedMessages, encryptionOrder: version };
     }
 
     await sleep(olmSessionUpdateRetryDelay);