diff --git a/keyserver/src/database/migration-config.js b/keyserver/src/database/migration-config.js
--- a/keyserver/src/database/migration-config.js
+++ b/keyserver/src/database/migration-config.js
@@ -325,6 +325,24 @@
       await dbQuery(SQL`DROP TABLE versions;`);
     },
   ],
+  [
+    31,
+    async () => {
+      await dbQuery(
+        SQL`
+        CREATE TABLE IF NOT EXISTS keyserver_hosted_olm_sessions (
+          cookie_id bigint(20) NOT NULL,
+          is_primary tinyint(1) NOT NULL,
+          pickled_olm_session text CHARACTER SET ascii COLLATE ascii_bin DEFAULT NULL
+        ) ENGINE=InnoDB DEFAULT CHARSET=ascii COLLATE=ascii_bin;
+
+        ALTER TABLE keyserver_hosted_olm_sessions
+          ADD PRIMARY KEY (cookie_id, is_primary);
+      `,
+        { multipleStatements: true },
+      );
+    },
+  ],
 ]);
 const newDatabaseVersion: number = Math.max(...migrations.keys());
 
diff --git a/keyserver/src/database/setup-db.js b/keyserver/src/database/setup-db.js
--- a/keyserver/src/database/setup-db.js
+++ b/keyserver/src/database/setup-db.js
@@ -249,6 +249,12 @@
         processed_content mediumtext COLLATE utf8mb4_bin
       ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_bin;
 
+      CREATE TABLE keyserver_hosted_olm_sessions (
+        cookie_id bigint(20) NOT NULL,
+        is_primary tinyint(1) NOT NULL,
+        pickled_olm_session text CHARACTER SET ascii COLLATE ascii_bin DEFAULT NULL
+      ) ENGINE=InnoDB DEFAULT CHARSET=ascii COLLATE=ascii_bin;
+
       ALTER TABLE cookies
         ADD PRIMARY KEY (id),
         ADD UNIQUE KEY device_token (device_token(512)),
@@ -368,6 +374,9 @@
       ALTER TABLE message_search
         ADD PRIMARY KEY (original_message_id),
         ADD FULLTEXT INDEX processed_content (processed_content);
+
+      ALTER TABLE keyserver_hosted_olm_sessions
+        ADD PRIMARY KEY (cookie_id, is_primary);
     `,
     { multipleStatements: true },
   );