diff --git a/keyserver/src/socket/tunnelbroker-socket.js b/keyserver/src/socket/tunnelbroker-socket.js
--- a/keyserver/src/socket/tunnelbroker-socket.js
+++ b/keyserver/src/socket/tunnelbroker-socket.js
@@ -33,6 +33,7 @@
   connected: boolean;
   promises: Promises;
   heartbeatTimeoutID: ?TimeoutID;
+  oneTimeKeysPromise: ?Promise<void>;
 
   constructor(socketURL: string, initMessage: ConnectionInitializationMessage) {
     this.connected = false;
@@ -108,7 +109,7 @@
         const messageToKeyserver = JSON.parse(payload);
         if (refreshKeysRequestValidator.is(messageToKeyserver)) {
           const request: RefreshKeyRequest = messageToKeyserver;
-          await uploadNewOneTimeKeys(request.numberOfKeys);
+          this.refreshOneTimeKeys(request.numberOfKeys);
         }
       } catch (e) {
         console.error(
@@ -150,6 +151,14 @@
     }
   };
 
+  refreshOneTimeKeys: (numberOfKeys: number) => void = numberOfKeys => {
+    const oldOneTimeKeysPromise = this.oneTimeKeysPromise;
+    this.oneTimeKeysPromise = (async () => {
+      await oldOneTimeKeysPromise;
+      await uploadNewOneTimeKeys(numberOfKeys);
+    })();
+  };
+
   sendMessage: (message: ClientMessageToDevice) => Promise<void> = (
     message: ClientMessageToDevice,
   ) => {