diff --git a/keyserver/src/deleters/upload-deleters.js b/keyserver/src/deleters/upload-deleters.js
--- a/keyserver/src/deleters/upload-deleters.js
+++ b/keyserver/src/deleters/upload-deleters.js
@@ -3,7 +3,9 @@
 import { ServerError } from 'lib/utils/errors.js';
 
 import { dbQuery, SQL } from '../database/database.js';
+import { deleteBlob, removeBlobHolders } from '../services/blob.js';
 import type { Viewer } from '../session/viewer.js';
+import { blobHoldersFromUploadRows } from '../uploads/media-utils.js';
 
 async function deleteUpload(viewer: Viewer, id: string): Promise<void> {
   if (!viewer.loggedIn) {
@@ -11,7 +13,7 @@
   }
 
   const fetchQuery = SQL`
-    SELECT uploader, container, user_container AS userContainer
+    SELECT uploader, container, user_container AS userContainer, extra
     FROM uploads
     WHERE id = ${id}
   `;
@@ -21,7 +23,7 @@
     throw new ServerError('invalid_parameters');
   }
   const [row] = result;
-  const { uploader, container, userContainer } = row;
+  const { uploader, container, userContainer, extra } = row;
 
   if (
     uploader.toString() !== viewer.userID ||
@@ -31,26 +33,47 @@
     throw new ServerError('invalid_parameters');
   }
 
+  const { blobHash, blobHolder } = JSON.parse(extra);
+  let holderRemovalPromise;
+  if (blobHash && blobHolder) {
+    holderRemovalPromise = deleteBlob({
+      hash: blobHash,
+      holder: blobHolder,
+    });
+  }
+
   const deleteQuery = SQL`
     DELETE u, i
     FROM uploads u
     LEFT JOIN ids i ON i.id = u.id
     WHERE u.id = ${id}
   `;
-  await dbQuery(deleteQuery);
+  await Promise.all([dbQuery(deleteQuery), holderRemovalPromise]);
 }
 
 const maxUnassignedUploadAge = 24 * 60 * 60 * 1000;
 async function deleteUnassignedUploads(): Promise<void> {
   const oldestUnassignedUploadToKeep = Date.now() - maxUnassignedUploadAge;
-  await dbQuery(SQL`
+
+  const holdersQuery = SQL`
+    SELECT extra
+    FROM uploads
+    WHERE container IS NULL
+      AND user_container IS NULL
+      AND creation_time < ${oldestUnassignedUploadToKeep}
+  `;
+  const [rows] = await dbQuery(holdersQuery);
+  const blobHolders = blobHoldersFromUploadRows(rows);
+
+  const deletionQuery = SQL`
     DELETE u, i
     FROM uploads u
     LEFT JOIN ids i ON i.id = u.id
     WHERE u.container IS NULL
       AND u.user_container IS NULL
       AND creation_time < ${oldestUnassignedUploadToKeep}
-  `);
+  `;
+  await Promise.all([dbQuery(deletionQuery), removeBlobHolders(blobHolders)]);
 }
 
 export { deleteUpload, deleteUnassignedUploads };
diff --git a/keyserver/src/uploads/media-utils.js b/keyserver/src/uploads/media-utils.js
--- a/keyserver/src/uploads/media-utils.js
+++ b/keyserver/src/uploads/media-utils.js
@@ -11,6 +11,7 @@
   mediaConfig,
 } from 'lib/media/file-utils.js';
 import { getImageProcessingPlan } from 'lib/media/image-utils.js';
+import type { BlobHashAndHolder } from 'lib/types/holder-types.js';
 import type { Dimensions } from 'lib/types/media-types.js';
 import { deepFileInfoFromData } from 'web/media/file-utils.js';
 
@@ -239,4 +240,21 @@
   };
 }
 
-export { getMediaType, validateAndConvert };
+function blobHoldersFromUploadRows(
+  rows: $ReadOnlyArray<Object>,
+): $ReadOnlyArray<BlobHashAndHolder> {
+  const results = [];
+  for (const { extra } of rows) {
+    if (!extra) {
+      continue;
+    }
+    const { blobHash, blobHolder } = JSON.parse(extra);
+    if (blobHash && blobHolder) {
+      results.push({ blobHash, holder: blobHolder });
+    }
+  }
+
+  return results;
+}
+
+export { blobHoldersFromUploadRows, getMediaType, validateAndConvert };