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
@@ -201,18 +201,23 @@
   cookieID: string,
   notification: AndroidNotification,
   notificationSizeValidator?: AndroidNotification => boolean,
+  blobHolder?: ?string,
 ): Promise<{
   +notification: AndroidNotification,
   +payloadSizeExceeded: boolean,
   +encryptionOrder?: number,
 }> {
-  const { id, keyserverID, badgeOnly, ...unencryptedPayload } =
-    notification.data;
+  const { id, keyserverID, badgeOnly, ...rest } = notification.data;
   let unencryptedData = { badgeOnly, keyserverID };
   if (id) {
     unencryptedData = { ...unencryptedData, id };
   }
 
+  let unencryptedPayload = rest;
+  if (blobHolder) {
+    unencryptedPayload = { ...unencryptedPayload, blobHolder };
+  }
+
   let payloadSizeValidator;
   if (notificationSizeValidator) {
     payloadSizeValidator = (
@@ -392,11 +397,12 @@
   }>,
 > {
   const notificationPromises = devices.map(
-    async ({ deviceToken, cookieID }) => {
+    async ({ deviceToken, cookieID, blobHolder }) => {
       const notif = await encryptAndroidNotification(
         cookieID,
         notification,
         notificationSizeValidator,
+        blobHolder,
       );
       return { deviceToken, cookieID, ...notif };
     },
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
@@ -1267,11 +1267,11 @@
     notificationsSizeValidator,
   );
 
-  const devicesWithExcessiveSize = notifsWithMessageInfos
+  const devicesWithExcessiveSizeNoHolders = notifsWithMessageInfos
     .filter(({ payloadSizeExceeded }) => payloadSizeExceeded)
     .map(({ cookieID, deviceToken }) => ({ cookieID, deviceToken }));
 
-  if (devicesWithExcessiveSize.length === 0) {
+  if (devicesWithExcessiveSizeNoHolders.length === 0) {
     return notifsWithMessageInfos.map(
       ({ notification: notif, deviceToken, encryptionOrder }) => ({
         notification: notif,
@@ -1285,12 +1285,13 @@
     native: NEXT_CODE_VERSION,
   });
 
-  let blobHash, encryptionKey, blobUploadError;
+  let blobHash, blobHolders, encryptionKey, blobUploadError;
   if (canQueryBlobService) {
-    ({ blobHash, encryptionKey, blobUploadError } = await blobServiceUpload(
-      JSON.stringify(copyWithMessageInfos.data),
-      1,
-    ));
+    ({ blobHash, blobHolders, encryptionKey, blobUploadError } =
+      await blobServiceUpload(
+        JSON.stringify(copyWithMessageInfos.data),
+        devicesWithExcessiveSizeNoHolders.length,
+      ));
   }
 
   if (blobUploadError) {
@@ -1300,12 +1301,23 @@
     );
   }
 
-  if (blobHash && encryptionKey) {
+  let devicesWithExcessiveSize = devicesWithExcessiveSizeNoHolders;
+  if (
+    blobHash &&
+    encryptionKey &&
+    blobHolders &&
+    blobHolders.length === devicesWithExcessiveSizeNoHolders.length
+  ) {
     notification.data = {
       ...notification.data,
       blobHash,
       encryptionKey,
     };
+
+    devicesWithExcessiveSize = blobHolders.map((holder, idx) => ({
+      ...devicesWithExcessiveSize[idx],
+      blobHolder: holder,
+    }));
   }
 
   const notifsWithoutMessageInfos = await prepareEncryptedAndroidNotifications(
diff --git a/native/android/app/build.gradle b/native/android/app/build.gradle
--- a/native/android/app/build.gradle
+++ b/native/android/app/build.gradle
@@ -709,6 +709,14 @@
     } else {
         implementation jscFlavor
     }
+
+    def work_version = "2.8.1"
+    // (Java only)
+    implementation "androidx.work:work-runtime:$work_version"
+    // Guava for listenable future to solve the bug:
+    // https://stackoverflow.com/questions/64290141/android-studio-class-file-for-com-google-common-util-concurrent-listenablefuture
+    // https://github.com/google/ExoPlayer/issues/7993
+    implementation "com.google.guava:guava:31.0.1-android"
 }
 
 if (isNewArchitectureEnabled()) {
diff --git a/native/android/app/src/main/java/app/comm/android/commservices/CommAndroidBlobClient.java b/native/android/app/src/main/java/app/comm/android/commservices/CommAndroidBlobClient.java
--- a/native/android/app/src/main/java/app/comm/android/commservices/CommAndroidBlobClient.java
+++ b/native/android/app/src/main/java/app/comm/android/commservices/CommAndroidBlobClient.java
@@ -1,5 +1,12 @@
 package app.comm.android.commservices;
 
+import android.content.Context;
+import androidx.work.Constraints;
+import androidx.work.Data;
+import androidx.work.NetworkType;
+import androidx.work.OneTimeWorkRequest;
+import androidx.work.WorkManager;
+import androidx.work.WorkRequest;
 import app.comm.android.BuildConfig;
 import app.comm.android.fbjni.CommSecureStore;
 import java.io.IOException;
@@ -15,9 +22,6 @@
 import org.json.JSONObject;
 
 public class CommAndroidBlobClient {
-  private static final String BLOB_SERVICE_URL = BuildConfig.DEBUG
-      ? "https://blob.staging.commtechnologies.org"
-      : "https://blob.commtechnologies.org";
   // The FirebaseMessagingService docs state that message
   // processing should complete within at most 20 seconds
   // window. Therefore we limit http time call to 15 seconds
@@ -25,11 +29,17 @@
   private static final int NOTIF_PROCESSING_TIME_LIMIT_SECONDS = 15;
   // OkHttp docs advise to share OkHttpClient instances
   // https://square.github.io/okhttp/4.x/okhttp/okhttp3/-ok-http-client/#okhttpclients-should-be-shared
-  private static final OkHttpClient httpClient =
+  public static final OkHttpClient httpClient =
       new OkHttpClient.Builder()
           .callTimeout(NOTIF_PROCESSING_TIME_LIMIT_SECONDS, TimeUnit.SECONDS)
           .build();
 
+  public static final String BLOB_SERVICE_URL = BuildConfig.DEBUG
+      ? "https://blob.staging.commtechnologies.org"
+      : "https://blob.commtechnologies.org";
+  public static final String BLOB_HASH_KEY = "blob_hash";
+  public static final String BLOB_HOLDER_KEY = "holder";
+
   public byte[] getBlobSync(String blobHash) throws IOException, JSONException {
     String authToken = getAuthToken();
     Request request = new Request.Builder()
@@ -47,7 +57,28 @@
     return response.body().bytes();
   }
 
-  private String getAuthToken() throws JSONException {
+  public void scheduleDeferredBlobDeletion(
+      String blobHash,
+      String blobHolder,
+      Context context) {
+    Constraints constraints = new Constraints.Builder()
+                                  .setRequiredNetworkType(NetworkType.CONNECTED)
+                                  .build();
+    WorkRequest deleteBlobWorkRequest =
+        new OneTimeWorkRequest.Builder(CommAndroidDeleteBlobWork.class)
+            .setConstraints(constraints)
+            .setInitialDelay(
+                NOTIF_PROCESSING_TIME_LIMIT_SECONDS, TimeUnit.SECONDS)
+            .setInputData(new Data.Builder()
+                              .putString(BLOB_HASH_KEY, blobHash)
+                              .putString(BLOB_HOLDER_KEY, blobHolder)
+                              .build())
+            .build();
+
+    WorkManager.getInstance(context).enqueue(deleteBlobWorkRequest);
+  }
+
+  public static String getAuthToken() throws JSONException {
     // Authentication data are retrieved on every request
     // since they might change while CommNotificationsHandler
     // thread is running so we should not rely on caching
diff --git a/native/android/app/src/main/java/app/comm/android/commservices/CommAndroidDeleteBlobWork.java b/native/android/app/src/main/java/app/comm/android/commservices/CommAndroidDeleteBlobWork.java
new file mode 100644
--- /dev/null
+++ b/native/android/app/src/main/java/app/comm/android/commservices/CommAndroidDeleteBlobWork.java
@@ -0,0 +1,96 @@
+package app.comm.android.commservices;
+
+import android.content.Context;
+import android.util.Log;
+import androidx.work.Data;
+import androidx.work.ListenableWorker.Result;
+import androidx.work.Worker;
+import androidx.work.WorkerParameters;
+import java.io.IOException;
+import java.util.function.Consumer;
+import okhttp3.MediaType;
+import okhttp3.Request;
+import okhttp3.RequestBody;
+import okhttp3.Response;
+import org.json.JSONException;
+import org.json.JSONObject;
+
+public class CommAndroidDeleteBlobWork extends Worker {
+
+  private static final int MAX_RETRY_ATTEMPTS = 10;
+
+  public CommAndroidDeleteBlobWork(Context context, WorkerParameters params) {
+    super(context, params);
+  }
+
+  @Override
+  public Result doWork() {
+    String blobHash =
+        getInputData().getString(CommAndroidBlobClient.BLOB_HASH_KEY);
+    String blobHolder =
+        getInputData().getString(CommAndroidBlobClient.BLOB_HOLDER_KEY);
+
+    String jsonBody;
+    try {
+      jsonBody = new JSONObject()
+                     .put(CommAndroidBlobClient.BLOB_HASH_KEY, blobHash)
+                     .put(CommAndroidBlobClient.BLOB_HOLDER_KEY, blobHolder)
+                     .toString();
+    } catch (JSONException e) {
+      // This should never happen since the code
+      // throwing is just simple JSON creation.
+      // If it happens there is no way to retry
+      // so we fail immediately.
+      Log.w(
+          "COMM",
+          "Failed to create JSON from blob hash and holder provided.",
+          e);
+      return Result.failure();
+    }
+
+    String authToken;
+    try {
+      authToken = CommAndroidBlobClient.getAuthToken();
+    } catch (JSONException e) {
+      // In this case however it may happen that
+      // auth metadata got corrupted but will be
+      // fixed soon by event emitter. Therefore
+      // we should retry in this case.
+      return Result.retry();
+    }
+
+    RequestBody requestBody =
+        RequestBody.create(MediaType.parse("application/json"), jsonBody);
+    Request request = new Request.Builder()
+                          .delete(requestBody)
+                          .url(CommAndroidBlobClient.BLOB_SERVICE_URL + "/blob")
+                          .header("Authorization", authToken)
+                          .build();
+
+    try {
+      Response response =
+          CommAndroidBlobClient.httpClient.newCall(request).execute();
+      if (response.isSuccessful()) {
+        return Result.success();
+      }
+      Log.w(
+          "COMM",
+          "Failed to execute blob deletion request. HTTP code:" +
+              response.code() + " status: " + response.message());
+      return retryOrFail();
+    } catch (IOException e) {
+      Log.w(
+          "COMM",
+          "IO exception occurred while issuing blob deletion request.",
+          e);
+      return retryOrFail();
+    }
+  }
+
+  private Result retryOrFail() {
+    if (getRunAttemptCount() > MAX_RETRY_ATTEMPTS) {
+      return Result.failure();
+    }
+    return Result.retry();
+  }
+}
diff --git a/native/android/app/src/main/java/app/comm/android/notifications/CommNotificationsHandler.java b/native/android/app/src/main/java/app/comm/android/notifications/CommNotificationsHandler.java
--- a/native/android/app/src/main/java/app/comm/android/notifications/CommNotificationsHandler.java
+++ b/native/android/app/src/main/java/app/comm/android/notifications/CommNotificationsHandler.java
@@ -50,6 +50,7 @@
   private static final String ENCRYPTED_PAYLOAD_KEY = "encryptedPayload";
   private static final String ENCRYPTION_FAILED_KEY = "encryptionFailed";
   private static final String BLOB_HASH_KEY = "blobHash";
+  private static final String BLOB_HOLDER_KEY = "blobHolder";
   private static final String AES_ENCRYPTION_KEY_LABEL = "encryptionKey";
   private static final String GROUP_NOTIF_IDS_KEY = "groupNotifIDs";
   private static final String COLLAPSE_ID_KEY = "collapseKey";
@@ -153,7 +154,8 @@
     }
 
     if (message.getData().get(BLOB_HASH_KEY) != null &&
-        message.getData().get(AES_ENCRYPTION_KEY_LABEL) != null) {
+        message.getData().get(AES_ENCRYPTION_KEY_LABEL) != null &&
+        message.getData().get(BLOB_HOLDER_KEY) != null) {
       handleLargeNotification(message);
     }
 
@@ -294,6 +296,7 @@
 
   private void handleLargeNotification(RemoteMessage message) {
     String blobHash = message.getData().get(BLOB_HASH_KEY);
+    String blobHolder = message.getData().get(BLOB_HOLDER_KEY);
     try {
       byte[] largePayload = blobClient.getBlobSync(blobHash);
       message = aesDecryptRemoteMessage(message, largePayload);
@@ -301,6 +304,8 @@
     } catch (Exception e) {
       Log.w("COMM", "Failure when handling large notification.", e);
     }
+    blobClient.scheduleDeferredBlobDeletion(
+        blobHash, blobHolder, this.getApplicationContext());
   }
 
   private void addToThreadGroupAndDisplay(