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
@@ -5,6 +5,7 @@
 
 import type {
   AndroidNotification,
+  AndroidNotificationPayload,
   AndroidNotificationRescind,
 } from './types.js';
 import { encryptAndUpdateOlmSession } from '../updaters/olm-session-updater.js';
@@ -70,42 +71,90 @@
 async function encryptAndroidNotificationPayload<T>(
   cookieID: string,
   unencryptedPayload: T,
-): Promise<T | { +encryptedPayload: string }> {
+  payloadSizeValidator?: (T | { +encryptedPayload: string }) => boolean,
+): Promise<{
+  +resultPayload: T | { +encryptedPayload: string },
+  +payloadSizeViolated: boolean,
+}> {
   try {
     const unencryptedSerializedPayload = JSON.stringify(unencryptedPayload);
     if (!unencryptedSerializedPayload) {
-      return unencryptedPayload;
+      return {
+        resultPayload: unencryptedPayload,
+        payloadSizeViolated: payloadSizeValidator
+          ? payloadSizeValidator(unencryptedPayload)
+          : false,
+      };
     }
+
+    let dbPersistCondition;
+    if (payloadSizeValidator) {
+      dbPersistCondition = ({ serializedPayload }) =>
+        payloadSizeValidator({ encryptedPayload: serializedPayload.body });
+    }
+
     const {
       encryptedMessages: { serializedPayload },
-    } = await encryptAndUpdateOlmSession(cookieID, 'notifications', {
-      serializedPayload: unencryptedSerializedPayload,
-    });
-    return { encryptedPayload: serializedPayload.body };
+      dbPersistConditionViolated,
+    } = await encryptAndUpdateOlmSession(
+      cookieID,
+      'notifications',
+      {
+        serializedPayload: unencryptedSerializedPayload,
+      },
+      dbPersistCondition,
+    );
+    return {
+      resultPayload: { encryptedPayload: serializedPayload.body },
+      payloadSizeViolated: !!dbPersistConditionViolated,
+    };
   } catch (e) {
     console.log('Notification encryption failed: ' + e);
-    return {
+    const resultPayload = {
       encryptionFailed: '1',
       ...unencryptedPayload,
     };
+    return {
+      resultPayload,
+      payloadSizeViolated: payloadSizeValidator
+        ? payloadSizeValidator(unencryptedPayload)
+        : false,
+    };
   }
 }
 
 async function encryptAndroidNotification(
   cookieID: string,
   notification: AndroidNotification,
-): Promise<AndroidNotification> {
+  notificationSizeValidator?: AndroidNotification => boolean,
+): Promise<{
+  +notification: AndroidNotification,
+  +payloadSizeViolated: boolean,
+}> {
   const { id, badgeOnly, ...unencryptedPayload } = notification.data;
-  const encryptedSerializedPayload = await encryptAndroidNotificationPayload(
-    cookieID,
-    unencryptedPayload,
-  );
+  let payloadSizeValidator;
+  if (notificationSizeValidator) {
+    payloadSizeValidator = (
+      payload: AndroidNotificationPayload | { +encryptedPayload: string },
+    ) => {
+      return notificationSizeValidator({ data: { id, badgeOnly, ...payload } });
+    };
+  }
+  const { resultPayload, payloadSizeViolated } =
+    await encryptAndroidNotificationPayload(
+      cookieID,
+      unencryptedPayload,
+      payloadSizeValidator,
+    );
   return {
-    data: {
-      id,
-      badgeOnly,
-      ...encryptedSerializedPayload,
+    notification: {
+      data: {
+        id,
+        badgeOnly,
+        ...resultPayload,
+      },
     },
+    payloadSizeViolated,
   };
 }
 
@@ -113,12 +162,15 @@
   cookieID: string,
   notification: AndroidNotificationRescind,
 ): Promise<AndroidNotificationRescind> {
-  const encryptedPayload = await encryptAndroidNotificationPayload(
+  // We don't validate payload size for rescind
+  // since they are expected to be small and
+  // never exceed any FCM limit
+  const { resultPayload } = await encryptAndroidNotificationPayload(
     cookieID,
     notification.data,
   );
   return {
-    data: encryptedPayload,
+    data: resultPayload,
   };
 }
 
@@ -135,9 +187,19 @@
 function prepareEncryptedAndroidNotifications(
   cookieIDs: $ReadOnlyArray<string>,
   notification: AndroidNotification,
-): Promise<$ReadOnlyArray<AndroidNotification>> {
+  notificationSizeValidator?: (notification: AndroidNotification) => boolean,
+): Promise<
+  $ReadOnlyArray<{
+    +notification: AndroidNotification,
+    +payloadSizeViolated: boolean,
+  }>,
+> {
   const notificationPromises = cookieIDs.map(cookieID =>
-    encryptAndroidNotification(cookieID, notification),
+    encryptAndroidNotification(
+      cookieID,
+      notification,
+      notificationSizeValidator,
+    ),
   );
   return Promise.all(notificationPromises);
 }
diff --git a/keyserver/src/push/send.js b/keyserver/src/push/send.js
--- a/keyserver/src/push/send.js
+++ b/keyserver/src/push/send.js
@@ -23,6 +23,7 @@
   rawThreadInfoFromServerThreadInfo,
   threadInfoFromRawThreadInfo,
 } from 'lib/shared/thread-utils.js';
+import { NEXT_CODE_VERSION } from 'lib/shared/version-utils.js';
 import type { Platform, PlatformDetails } from 'lib/types/device-types.js';
 import { messageTypes } from 'lib/types/message-types-enum.js';
 import {
@@ -54,6 +55,7 @@
 } from './types.js';
 import {
   apnPush,
+  blobServiceUpload,
   fcmPush,
   getUnreadCounts,
   apnMaxNotificationPayloadByteSize,
@@ -814,44 +816,107 @@
     data: { ...notification.data, messageInfos },
   };
 
-  const evaluateAndSelectNotification = (notif, notifWithMessageInfos) => {
-    if (
-      Buffer.byteLength(JSON.stringify(notifWithMessageInfos)) <=
-      fcmMaxNotificationPayloadByteSize
-    ) {
-      return notifWithMessageInfos;
-    }
-    if (
-      Buffer.byteLength(JSON.stringify(notif)) >
+  const deviceTokens = devices.map(({ deviceToken }) => deviceToken);
+
+  if (!shouldBeEncrypted) {
+    const notificationToSend =
+      Buffer.byteLength(JSON.stringify(copyWithMessageInfos)) <=
       fcmMaxNotificationPayloadByteSize
-    ) {
-      console.warn(
-        `Android notification ${notifID} exceeds size limit, even with messageInfos omitted`,
-      );
-    }
-    return notif;
-  };
+        ? copyWithMessageInfos
+        : notification;
 
-  const deviceTokens = devices.map(({ deviceToken }) => deviceToken);
-  if (shouldBeEncrypted) {
-    const cookieIDs = devices.map(({ cookieID }) => cookieID);
-    const [notifications, notificationsWithMessageInfos] = await Promise.all([
-      prepareEncryptedAndroidNotifications(cookieIDs, notification),
-      prepareEncryptedAndroidNotifications(cookieIDs, copyWithMessageInfos),
-    ]);
-    return notificationsWithMessageInfos.map((notif, idx) => ({
-      notification: evaluateAndSelectNotification(notifications[idx], notif),
-      deviceToken: deviceTokens[idx],
+    return deviceTokens.map(deviceToken => ({
+      notification: notificationToSend,
+      deviceToken,
     }));
   }
-  const notificationToSend = evaluateAndSelectNotification(
-    notification,
-    copyWithMessageInfos,
+
+  const cookieIDs = devices.map(({ cookieID }) => cookieID);
+
+  const notificationsSizeValidator = notif => {
+    const serializedNotif = JSON.stringify(notif);
+    return (
+      !serializedNotif ||
+      Buffer.byteLength(serializedNotif) <= fcmMaxNotificationPayloadByteSize
+    );
+  };
+
+  const notificationsWithMessageInfos =
+    await prepareEncryptedAndroidNotifications(
+      cookieIDs,
+      copyWithMessageInfos,
+      notificationsSizeValidator,
+    );
+
+  const cookieIDsWithSizeViolation = notificationsWithMessageInfos
+    .filter(({ payloadSizeViolated }) => payloadSizeViolated)
+    .map((_, idx) => cookieIDs[idx]);
+
+  if (cookieIDsWithSizeViolation.length === 0) {
+    return notificationsWithMessageInfos.map(
+      ({ notification: notif }, idx) => ({
+        notification: notif,
+        deviceToken: deviceTokens[idx],
+      }),
+    );
+  }
+  const canQueryBlobService = codeVersion && codeVersion >= NEXT_CODE_VERSION;
+  let blobHash, encryptionKey, blobUploadError;
+  if (canQueryBlobService) {
+    ({
+      blobHash: blobHash,
+      encryptionKey: encryptionKey,
+      blobUploadError: blobUploadError,
+    } = await blobServiceUpload(JSON.stringify(copyWithMessageInfos.data)));
+  }
+
+  if (blobUploadError) {
+    console.warn(
+      `Failed to upload payload of notification: ${notifID} ` +
+        `due to error: ${blobUploadError}`,
+    );
+  }
+
+  if (!blobHash || !encryptionKey) {
+    const notificationsWithoutMessageInfos =
+      await prepareEncryptedAndroidNotifications(
+        cookieIDsWithSizeViolation,
+        notification,
+      );
+
+    return notificationsWithMessageInfos.map(
+      ({ notification: notif, payloadSizeViolated }, idx) => ({
+        notification: payloadSizeViolated
+          ? notificationsWithoutMessageInfos[idx].notification
+          : notif,
+        deviceToken: deviceTokens[idx],
+      }),
+    );
+  }
+
+  const blobMetadataNotifications = await prepareEncryptedAndroidNotifications(
+    cookieIDsWithSizeViolation,
+    {
+      data: {
+        id: notifID,
+        badge: unreadCount.toString(),
+        badgeOnly: badgeOnly ? '1' : '0',
+        threadID,
+        blobHash,
+        encryptionKey,
+        ...rest,
+      },
+    },
+  );
+
+  return notificationsWithMessageInfos.map(
+    ({ notification: notif, payloadSizeViolated }, idx) => ({
+      notification: payloadSizeViolated
+        ? blobMetadataNotifications[idx].notification
+        : notif,
+      deviceToken: deviceTokens[idx],
+    }),
   );
-  return deviceTokens.map(deviceToken => ({
-    notification: notificationToSend,
-    deviceToken,
-  }));
 }
 
 type WebNotifInputData = {
@@ -1273,9 +1338,10 @@
         const cookieIDs = deviceInfos.map(({ cookieID }) => cookieID);
         let notificationsArray;
         if (codeVersion > 222) {
-          notificationsArray = await prepareEncryptedAndroidNotifications(
-            cookieIDs,
-            notification,
+          const notificationsWithPayloadViolatedInfo =
+            await prepareEncryptedAndroidNotifications(cookieIDs, notification);
+          notificationsArray = notificationsWithPayloadViolatedInfo.map(
+            ({ notification: notif }) => notif,
           );
         } else {
           notificationsArray = cookieIDs.map(() => notification);
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
@@ -7,16 +7,26 @@
   +deviceToken: string,
 };
 
-type AndroidNotificationPayload = {
+type AndroidNotificationPayloadBase = {
   +badge: string,
   +body?: string,
   +title?: string,
   +prefix?: string,
   +threadID?: string,
-  +messageInfos?: string,
   +encryptionFailed?: '1',
 };
 
+export type AndroidNotificationPayload =
+  | {
+      ...AndroidNotificationPayloadBase,
+      +messageInfos?: string,
+    }
+  | {
+      ...AndroidNotificationPayloadBase,
+      +blobHash: string,
+      +encryptionKey: string,
+    };
+
 export type AndroidNotification = {
   +data: {
     +id?: string,