diff --git a/keyserver/src/cron/cron.js b/keyserver/src/cron/cron.js
--- a/keyserver/src/cron/cron.js
+++ b/keyserver/src/cron/cron.js
@@ -1,5 +1,6 @@
 // @flow
 
+import type { Account as OlmAccount } from '@commapp/olm';
 import cluster from 'cluster';
 import schedule from 'node-schedule';
 
@@ -25,7 +26,7 @@
 import { deleteExpiredUpdates } from '../deleters/update-deleters.js';
 import { deleteUnassignedUploads } from '../deleters/upload-deleters.js';
 import { fetchCallUpdateOlmAccount } from '../updaters/olm-account-updater.js';
-import { validateAccountPrekey } from '../utils/olm-utils.js';
+import { validateAndUploadAccountPrekeys } from '../utils/olm-utils.js';
 
 if (cluster.isMaster) {
   schedule.scheduleJob(
@@ -111,8 +112,15 @@
     '0 0 * * *', // every day at midnight in the keyserver's timezone
     async () => {
       try {
-        await fetchCallUpdateOlmAccount('content', validateAccountPrekey);
-        await fetchCallUpdateOlmAccount('notifications', validateAccountPrekey);
+        await fetchCallUpdateOlmAccount(
+          'content',
+          (contentAccount: OlmAccount) =>
+            fetchCallUpdateOlmAccount(
+              'notifications',
+              (notifAccount: OlmAccount) =>
+                validateAndUploadAccountPrekeys(contentAccount, notifAccount),
+            ),
+        );
       } catch (e) {
         console.warn('encountered error while trying to validate prekeys', e);
       }
diff --git a/keyserver/src/utils/olm-utils.js b/keyserver/src/utils/olm-utils.js
--- a/keyserver/src/utils/olm-utils.js
+++ b/keyserver/src/utils/olm-utils.js
@@ -197,6 +197,68 @@
   return { prekey, prekeySignature };
 }
 
+async function validateAndUploadAccountPrekeys(
+  contentAccount: OlmAccount,
+  notifAccount: OlmAccount,
+): Promise<void> {
+  // Since keys are rotated synchronously, only check validity of one
+  if (shouldRotatePrekey(contentAccount)) {
+    await publishNewPrekeys(contentAccount, notifAccount);
+  }
+  if (shouldForgetPrekey(contentAccount)) {
+    contentAccount.forget_old_prekey();
+    notifAccount.forget_old_prekey();
+  }
+}
+
+async function publishNewPrekeys(
+  contentAccount: OlmAccount,
+  notifAccount: OlmAccount,
+): Promise<void> {
+  const rustAPIPromise = getRustAPI();
+  const fetchIdentityInfoPromise = fetchIdentityInfo();
+
+  const deviceID = JSON.parse(contentAccount.identity_keys()).ed25519;
+
+  contentAccount.generate_prekey();
+  const { prekey: contentPrekey, prekeySignature: contentPrekeySignature } =
+    getAccountPrekeysSet(contentAccount);
+
+  notifAccount.generate_prekey();
+  const { prekey: notifPrekey, prekeySignature: notifPrekeySignature } =
+    getAccountPrekeysSet(notifAccount);
+
+  if (!contentPrekeySignature || !notifPrekeySignature) {
+    console.warn('Unable to create valid signature for a prekey');
+    return;
+  }
+
+  const [rustAPI, identityInfo] = await Promise.all([
+    rustAPIPromise,
+    fetchIdentityInfoPromise,
+  ]);
+
+  if (!identityInfo) {
+    console.warn(
+      'Attempted to refresh prekeys before registering with Identity service',
+    );
+    return;
+  }
+
+  await rustAPI.publishPrekeys(
+    identityInfo.userId,
+    deviceID,
+    identityInfo.accessToken,
+    contentPrekey,
+    contentPrekeySignature,
+    notifPrekey,
+    notifPrekeySignature,
+  );
+
+  contentAccount.mark_prekey_as_published();
+  notifAccount.mark_prekey_as_published();
+}
+
 export {
   createPickledOlmAccount,
   createPickledOlmSession,
@@ -207,4 +269,5 @@
   uploadNewOneTimeKeys,
   getContentSigningKey,
   getAccountPrekeysSet,
+  validateAndUploadAccountPrekeys,
 };