diff --git a/src/dawn_wire/client/ClientDoers.cpp b/src/dawn_wire/client/ClientDoers.cpp
index a5ef7f6..2c6e23f 100644
--- a/src/dawn_wire/client/ClientDoers.cpp
+++ b/src/dawn_wire/client/ClientDoers.cpp
@@ -66,7 +66,6 @@
         if (buffer == nullptr) {
             return true;
         }
-
         return buffer->OnMapAsyncCallback(requestSerial, status, readInitialDataInfoLength,
                                           readInitialDataInfo);
     }
@@ -88,9 +87,17 @@
         if (fence == nullptr) {
             return true;
         }
+        return fence->OnCompletionCallback(requestSerial, status);
+    }
 
-        fence->OnCompletionCallback(requestSerial, status);
-        return true;
+    bool Client::DoQueueWorkDoneCallback(Queue* queue,
+                                         uint64_t requestSerial,
+                                         WGPUQueueWorkDoneStatus status) {
+        // The queue might have been deleted or recreated so this isn't an error.
+        if (queue == nullptr) {
+            return true;
+        }
+        return queue->OnWorkDoneCallback(requestSerial, status);
     }
 
     bool Client::DoDeviceCreateComputePipelineAsyncCallback(Device* device,
diff --git a/src/dawn_wire/client/Fence.cpp b/src/dawn_wire/client/Fence.cpp
index d9a858a..563f13f1 100644
--- a/src/dawn_wire/client/Fence.cpp
+++ b/src/dawn_wire/client/Fence.cpp
@@ -46,7 +46,8 @@
                              WGPUFenceOnCompletionCallback callback,
                              void* userdata) {
         if (client->IsDisconnected()) {
-            return callback(WGPUFenceCompletionStatus_DeviceLost, userdata);
+            callback(WGPUFenceCompletionStatus_DeviceLost, userdata);
+            return;
         }
 
         uint32_t serial = mOnCompletionRequestSerial++;
diff --git a/src/dawn_wire/client/Queue.cpp b/src/dawn_wire/client/Queue.cpp
index f5f68f7..8c9f78b 100644
--- a/src/dawn_wire/client/Queue.cpp
+++ b/src/dawn_wire/client/Queue.cpp
@@ -19,6 +19,47 @@
 
 namespace dawn_wire { namespace client {
 
+    Queue::~Queue() {
+        ClearAllCallbacks(WGPUQueueWorkDoneStatus_Unknown);
+    }
+
+    bool Queue::OnWorkDoneCallback(uint64_t requestSerial, WGPUQueueWorkDoneStatus status) {
+        auto requestIt = mOnWorkDoneRequests.find(requestSerial);
+        if (requestIt == mOnWorkDoneRequests.end()) {
+            return false;
+        }
+
+        // Remove the request data so that the callback cannot be called again.
+        // ex.) inside the callback: if the queue is deleted (when there are multiple queues),
+        // all callbacks reject.
+        OnWorkDoneData request = std::move(requestIt->second);
+        mOnWorkDoneRequests.erase(requestIt);
+
+        request.callback(status, request.userdata);
+        return true;
+    }
+
+    void Queue::OnSubmittedWorkDone(uint64_t signalValue,
+                                    WGPUQueueWorkDoneCallback callback,
+                                    void* userdata) {
+        if (client->IsDisconnected()) {
+            callback(WGPUQueueWorkDoneStatus_DeviceLost, userdata);
+            return;
+        }
+
+        uint32_t serial = mOnWorkDoneSerial++;
+        ASSERT(mOnWorkDoneRequests.find(serial) == mOnWorkDoneRequests.end());
+
+        QueueOnSubmittedWorkDoneCmd cmd;
+        cmd.queueId = this->id;
+        cmd.signalValue = signalValue;
+        cmd.requestSerial = serial;
+
+        mOnWorkDoneRequests[serial] = {callback, userdata};
+
+        client->SerializeCommand(cmd);
+    }
+
     WGPUFence Queue::CreateFence(WGPUFenceDescriptor const* descriptor) {
         auto* allocation = client->FenceAllocator().New(client);
 
@@ -65,4 +106,17 @@
         client->SerializeCommand(cmd);
     }
 
+    void Queue::CancelCallbacksForDisconnect() {
+        ClearAllCallbacks(WGPUQueueWorkDoneStatus_DeviceLost);
+    }
+
+    void Queue::ClearAllCallbacks(WGPUQueueWorkDoneStatus status) {
+        for (auto& it : mOnWorkDoneRequests) {
+            if (it.second.callback) {
+                it.second.callback(status, it.second.userdata);
+            }
+        }
+        mOnWorkDoneRequests.clear();
+    }
+
 }}  // namespace dawn_wire::client
diff --git a/src/dawn_wire/client/Queue.h b/src/dawn_wire/client/Queue.h
index 91c9393..f14fae1 100644
--- a/src/dawn_wire/client/Queue.h
+++ b/src/dawn_wire/client/Queue.h
@@ -27,7 +27,14 @@
     class Queue final : public ObjectBase {
       public:
         using ObjectBase::ObjectBase;
+        ~Queue();
 
+        bool OnWorkDoneCallback(uint64_t requestSerial, WGPUQueueWorkDoneStatus status);
+
+        // Dawn API
+        void OnSubmittedWorkDone(uint64_t signalValue,
+                                 WGPUQueueWorkDoneCallback callback,
+                                 void* userdata);
         WGPUFence CreateFence(const WGPUFenceDescriptor* descriptor);
         void WriteBuffer(WGPUBuffer cBuffer, uint64_t bufferOffset, const void* data, size_t size);
         void WriteTexture(const WGPUTextureCopyView* destination,
@@ -35,6 +42,18 @@
                           size_t dataSize,
                           const WGPUTextureDataLayout* dataLayout,
                           const WGPUExtent3D* writeSize);
+
+      private:
+        void CancelCallbacksForDisconnect() override;
+
+        void ClearAllCallbacks(WGPUQueueWorkDoneStatus status);
+
+        struct OnWorkDoneData {
+            WGPUQueueWorkDoneCallback callback = nullptr;
+            void* userdata = nullptr;
+        };
+        uint64_t mOnWorkDoneSerial = 0;
+        std::map<uint64_t, OnWorkDoneData> mOnWorkDoneRequests;
     };
 
 }}  // namespace dawn_wire::client