diff --git a/keyserver/src/creators/account-creator.js b/keyserver/src/creators/account-creator.js
--- a/keyserver/src/creators/account-creator.js
+++ b/keyserver/src/creators/account-creator.js
@@ -1,6 +1,7 @@
 // @flow
 
 import invariant from 'invariant';
+import { getRustAPI } from 'rust-node-addon';
 import bcrypt from 'twin-bcrypt';
 
 import ashoat from 'lib/facts/ashoat.js';
@@ -16,7 +17,10 @@
   RegisterResponse,
   RegisterRequest,
 } from 'lib/types/account-types.js';
-import type { SignedIdentityKeysBlob } from 'lib/types/crypto-types.js';
+import type {
+  ReservedUsernameMessage,
+  SignedIdentityKeysBlob,
+} from 'lib/types/crypto-types.js';
 import type {
   PlatformDetails,
   DeviceTokenUpdateRequest,
@@ -46,9 +50,11 @@
   fetchKnownUserInfos,
 } from '../fetchers/user-fetchers.js';
 import { verifyCalendarQueryThreadIDs } from '../responders/entry-responders.js';
+import { handleAsyncPromise } from '../responders/handlers.js';
 import { createNewUserCookie, setNewSession } from '../session/cookies.js';
 import { createScriptViewer } from '../session/scripts.js';
 import type { Viewer } from '../session/viewer.js';
+import { fetchOlmAccount } from '../updaters/olm-account-updater.js';
 import { updateThread } from '../updaters/thread-updaters.js';
 import { viewerAcknowledgmentUpdater } from '../updaters/viewer-acknowledgment-updater.js';
 
@@ -209,6 +215,24 @@
     ...messageInfos,
   ];
 
+  const issuedAt = new Date().toISOString();
+  const payload: $ReadOnlyArray<string> = [request.username];
+  const reservedUsernameMessage: ReservedUsernameMessage = {
+    statement: 'Add the following usernames to reserved list',
+    payload,
+    issuedAt,
+  };
+  const stringifiedMessage = JSON.stringify(reservedUsernameMessage);
+
+  handleAsyncPromise(
+    (async () => {
+      const rustAPI = await getRustAPI();
+      const accountInfo = await fetchOlmAccount('content');
+      const signature = accountInfo.account.sign(stringifiedMessage);
+      await rustAPI.addReservedUsernames(stringifiedMessage, signature);
+    })(),
+  );
+
   return {
     id,
     rawMessageInfos,
diff --git a/keyserver/src/deleters/account-deleters.js b/keyserver/src/deleters/account-deleters.js
--- a/keyserver/src/deleters/account-deleters.js
+++ b/keyserver/src/deleters/account-deleters.js
@@ -1,11 +1,13 @@
 // @flow
 
+import { getRustAPI } from 'rust-node-addon';
 import bcrypt from 'twin-bcrypt';
 
 import type {
   LogOutResponse,
   DeleteAccountRequest,
 } from 'lib/types/account-types.js';
+import type { ReservedUsernameMessage } from 'lib/types/crypto-types.js';
 import { updateTypes } from 'lib/types/update-types-enum.js';
 import type { UserInfo } from 'lib/types/user-types.js';
 import { ServerError } from 'lib/utils/errors.js';
@@ -14,11 +16,15 @@
 
 import { createUpdates } from '../creators/update-creator.js';
 import { dbQuery, SQL } from '../database/database.js';
-import { fetchKnownUserInfos } from '../fetchers/user-fetchers.js';
+import {
+  fetchKnownUserInfos,
+  fetchUsername,
+} from '../fetchers/user-fetchers.js';
 import { rescindPushNotifs } from '../push/rescind.js';
 import { handleAsyncPromise } from '../responders/handlers.js';
 import { createNewAnonymousCookie } from '../session/cookies.js';
 import type { Viewer } from '../session/viewer.js';
+import { fetchOlmAccount } from '../updaters/olm-account-updater.js';
 
 async function deleteAccount(
   viewer: Viewer,
@@ -99,7 +105,27 @@
       deviceToken: viewer.deviceToken,
     });
   }
-  const { anonymousViewerData } = await promiseAll(promises);
+  promises.username = fetchUsername(deletedUserID);
+  const { anonymousViewerData, username } = await promiseAll(promises);
+  if (username) {
+    const issuedAt = new Date().toISOString();
+    const reservedUsernameMessage: ReservedUsernameMessage = {
+      statement: 'Remove the following username from reserved list',
+      payload: username,
+      issuedAt,
+    };
+    const message = JSON.stringify(reservedUsernameMessage);
+
+    handleAsyncPromise(
+      (async () => {
+        const rustAPI = await getRustAPI();
+        const accountInfo = await fetchOlmAccount('content');
+        const signature = accountInfo.account.sign(message);
+        await rustAPI.removeReservedUsername(message, signature);
+      })(),
+    );
+  }
+
   if (anonymousViewerData) {
     viewer.setNewCookie(anonymousViewerData);
   }
diff --git a/lib/types/crypto-types.js b/lib/types/crypto-types.js
--- a/lib/types/crypto-types.js
+++ b/lib/types/crypto-types.js
@@ -38,6 +38,20 @@
   +signature: string,
 };
 
+// This type should not be changed without making equivalent changes to
+// `Message` in Identity service's `reserved_users` module
+export type ReservedUsernameMessage =
+  | {
+      +statement: 'Add the following usernames to reserved list',
+      +payload: $ReadOnlyArray<string>,
+      +issuedAt: string,
+    }
+  | {
+      +statement: 'Remove the following username from reserved list',
+      +payload: string,
+      +issuedAt: string,
+    };
+
 export const olmEncryptedMessageTypes = Object.freeze({
   PREKEY: 0,
   TEXT: 1,
diff --git a/services/identity/src/reserved_users.rs b/services/identity/src/reserved_users.rs
--- a/services/identity/src/reserved_users.rs
+++ b/services/identity/src/reserved_users.rs
@@ -7,6 +7,8 @@
 
 use crate::config::CONFIG;
 
+// This type should not be changed without making equivalent changes to
+// `ReservedUsernameMessage` in lib/types/crypto-types.js
 #[derive(Deserialize)]
 #[serde(rename_all = "camelCase")]
 struct Message<T> {