diff --git a/dawn_wire.json b/dawn_wire.json
index 0c59c42..a5b7064 100644
--- a/dawn_wire.json
+++ b/dawn_wire.json
@@ -47,6 +47,11 @@
             { "name": "object type", "type": "ObjectType" },
             { "name": "object id", "type": "ObjectId" }
         ],
+        "fence on completion": [
+            { "name": "fence id", "type": "ObjectId" },
+            { "name": "value", "type": "uint64_t" },
+            { "name": "request serial", "type": "uint64_t" }
+        ],
         "queue write buffer internal": [
             {"name": "queue id", "type": "ObjectId" },
             {"name": "buffer id", "type": "ObjectId" },
@@ -83,6 +88,11 @@
             { "name": "type", "type": "error type" },
             { "name": "message", "type": "char", "annotation": "const*", "length": "strlen" }
         ],
+        "fence on completion callback": [
+            { "name": "fence", "type": "ObjectHandle", "handle_type": "fence" },
+            { "name": "request serial", "type": "uint64_t" },
+            { "name": "status", "type": "fence completion status" }
+        ],
         "fence update completed value": [
             { "name": "fence", "type": "ObjectHandle", "handle_type": "fence" },
             { "name": "value", "type": "uint64_t" }
@@ -114,8 +124,7 @@
             "DeviceGetDefaultQueue",
             "DeviceInjectError",
             "DevicePushErrorScope",
-            "QueueCreateFence",
-            "QueueSignal"
+            "QueueCreateFence"
         ],
         "client_special_objects": [
             "Buffer",
diff --git a/src/dawn_wire/client/ClientDoers.cpp b/src/dawn_wire/client/ClientDoers.cpp
index 7fdabc0..c13f715 100644
--- a/src/dawn_wire/client/ClientDoers.cpp
+++ b/src/dawn_wire/client/ClientDoers.cpp
@@ -70,4 +70,16 @@
         return true;
     }
 
+    bool Client::DoFenceOnCompletionCallback(Fence* fence,
+                                             uint64_t requestSerial,
+                                             WGPUFenceCompletionStatus status) {
+        // The fence might have been deleted or recreated so this isn't an error.
+        if (fence == nullptr) {
+            return true;
+        }
+
+        fence->OnCompletionCallback(requestSerial, status);
+        return true;
+    }
+
 }}  // namespace dawn_wire::client
diff --git a/src/dawn_wire/client/Fence.cpp b/src/dawn_wire/client/Fence.cpp
index d9e1fa7..329998f 100644
--- a/src/dawn_wire/client/Fence.cpp
+++ b/src/dawn_wire/client/Fence.cpp
@@ -14,6 +14,7 @@
 
 #include "dawn_wire/client/Fence.h"
 
+#include "dawn_wire/client/Client.h"
 #include "dawn_wire/client/Device.h"
 
 namespace dawn_wire { namespace client {
@@ -21,67 +22,61 @@
     Fence::~Fence() {
         // Callbacks need to be fired in all cases, as they can handle freeing resources
         // so we call them with "Unknown" status.
-        for (auto& request : mRequests.IterateAll()) {
-            request.completionCallback(WGPUFenceCompletionStatus_Unknown, request.userdata);
+        for (auto& it : mOnCompletionRequests) {
+            if (it.second.callback) {
+                it.second.callback(WGPUFenceCompletionStatus_Unknown, it.second.userdata);
+            }
         }
-        mRequests.Clear();
+        mOnCompletionRequests.clear();
     }
 
     void Fence::Initialize(Queue* queue, const WGPUFenceDescriptor* descriptor) {
         mQueue = queue;
 
-        uint64_t initialValue = descriptor != nullptr ? descriptor->initialValue : 0u;
-        mSignaledValue = initialValue;
-        mCompletedValue = initialValue;
-    }
-
-    void Fence::CheckPassedFences() {
-        for (auto& request : mRequests.IterateUpTo(mCompletedValue)) {
-            request.completionCallback(WGPUFenceCompletionStatus_Success, request.userdata);
-        }
-        mRequests.ClearUpTo(mCompletedValue);
+        mCompletedValue = descriptor != nullptr ? descriptor->initialValue : 0u;
     }
 
     void Fence::OnCompletion(uint64_t value,
                              WGPUFenceOnCompletionCallback callback,
                              void* userdata) {
-        if (value > mSignaledValue) {
-            device->InjectError(WGPUErrorType_Validation,
-                                "Value greater than fence signaled value");
-            callback(WGPUFenceCompletionStatus_Error, userdata);
-            return;
-        }
+        uint32_t serial = mOnCompletionRequestSerial++;
+        ASSERT(mOnCompletionRequests.find(serial) == mOnCompletionRequests.end());
 
-        if (value <= mCompletedValue) {
-            callback(WGPUFenceCompletionStatus_Success, userdata);
-            return;
-        }
+        FenceOnCompletionCmd cmd;
+        cmd.fenceId = this->id;
+        cmd.value = value;
+        cmd.requestSerial = serial;
 
-        Fence::OnCompletionData request;
-        request.completionCallback = callback;
-        request.userdata = userdata;
-        mRequests.Enqueue(std::move(request), value);
+        mOnCompletionRequests[serial] = {callback, userdata};
+
+        this->device->GetClient()->SerializeCommand(cmd);
     }
 
     void Fence::OnUpdateCompletedValueCallback(uint64_t value) {
         mCompletedValue = value;
-        CheckPassedFences();
+    }
+
+    bool Fence::OnCompletionCallback(uint64_t requestSerial, WGPUFenceCompletionStatus status) {
+        auto requestIt = mOnCompletionRequests.find(requestSerial);
+        if (requestIt == mOnCompletionRequests.end()) {
+            return false;
+        }
+
+        // Remove the request data so that the callback cannot be called again.
+        // ex.) inside the callback: if the fence is deleted, all callbacks reject.
+        OnCompletionData request = std::move(requestIt->second);
+        mOnCompletionRequests.erase(requestIt);
+
+        request.callback(status, request.userdata);
+        return true;
     }
 
     uint64_t Fence::GetCompletedValue() const {
         return mCompletedValue;
     }
 
-    uint64_t Fence::GetSignaledValue() const {
-        return mSignaledValue;
-    }
-
     Queue* Fence::GetQueue() const {
         return mQueue;
     }
 
-    void Fence::SetSignaledValue(uint64_t value) {
-        mSignaledValue = value;
-    }
-
 }}  // namespace dawn_wire::client
diff --git a/src/dawn_wire/client/Fence.h b/src/dawn_wire/client/Fence.h
index 107b4e7..58d89c3 100644
--- a/src/dawn_wire/client/Fence.h
+++ b/src/dawn_wire/client/Fence.h
@@ -33,22 +33,20 @@
         void CheckPassedFences();
         void OnCompletion(uint64_t value, WGPUFenceOnCompletionCallback callback, void* userdata);
         void OnUpdateCompletedValueCallback(uint64_t value);
+        bool OnCompletionCallback(uint64_t requestSerial, WGPUFenceCompletionStatus status);
 
         uint64_t GetCompletedValue() const;
-        uint64_t GetSignaledValue() const;
         Queue* GetQueue() const;
 
-        void SetSignaledValue(uint64_t value);
-
       private:
         struct OnCompletionData {
-            WGPUFenceOnCompletionCallback completionCallback = nullptr;
+            WGPUFenceOnCompletionCallback callback = nullptr;
             void* userdata = nullptr;
         };
         Queue* mQueue = nullptr;
-        uint64_t mSignaledValue = 0;
         uint64_t mCompletedValue = 0;
-        SerialMap<OnCompletionData> mRequests;
+        uint64_t mOnCompletionRequestSerial = 0;
+        std::map<uint64_t, OnCompletionData> mOnCompletionRequests;
     };
 
 }}  // namespace dawn_wire::client
diff --git a/src/dawn_wire/client/Queue.cpp b/src/dawn_wire/client/Queue.cpp
index ad11673..52de14c 100644
--- a/src/dawn_wire/client/Queue.cpp
+++ b/src/dawn_wire/client/Queue.cpp
@@ -33,29 +33,6 @@
         return ToAPI(fence);
     }
 
-    void Queue::Signal(WGPUFence cFence, uint64_t signalValue) {
-        Fence* fence = FromAPI(cFence);
-        if (fence->GetQueue() != this) {
-            device->InjectError(WGPUErrorType_Validation,
-                                "Fence must be signaled on the queue on which it was created.");
-            return;
-        }
-        if (signalValue <= fence->GetSignaledValue()) {
-            device->InjectError(WGPUErrorType_Validation,
-                                "Fence value less than or equal to signaled value");
-            return;
-        }
-
-        fence->SetSignaledValue(signalValue);
-
-        QueueSignalCmd cmd;
-        cmd.self = ToAPI(this);
-        cmd.fence = cFence;
-        cmd.signalValue = signalValue;
-
-        device->GetClient()->SerializeCommand(cmd);
-    }
-
     void Queue::WriteBuffer(WGPUBuffer cBuffer,
                             uint64_t bufferOffset,
                             const void* data,
diff --git a/src/dawn_wire/client/Queue.h b/src/dawn_wire/client/Queue.h
index 866bccd..9e50348 100644
--- a/src/dawn_wire/client/Queue.h
+++ b/src/dawn_wire/client/Queue.h
@@ -29,7 +29,6 @@
         using ObjectBase::ObjectBase;
 
         WGPUFence CreateFence(const WGPUFenceDescriptor* descriptor);
-        void Signal(WGPUFence fence, uint64_t signalValue);
         void WriteBuffer(WGPUBuffer cBuffer, uint64_t bufferOffset, const void* data, size_t size);
         void WriteTexture(const WGPUTextureCopyView* destination,
                           const void* data,
diff --git a/src/dawn_wire/server/Server.h b/src/dawn_wire/server/Server.h
index 8049e80..2859714 100644
--- a/src/dawn_wire/server/Server.h
+++ b/src/dawn_wire/server/Server.h
@@ -48,6 +48,12 @@
         uint64_t value;
     };
 
+    struct FenceOnCompletionUserdata {
+        Server* server;
+        ObjectHandle fence;
+        uint64_t requestSerial;
+    };
+
     class Server : public ServerBase {
       public:
         Server(WGPUDevice device,
@@ -77,6 +83,7 @@
         static void ForwardPopErrorScope(WGPUErrorType type, const char* message, void* userdata);
         static void ForwardBufferMapAsync(WGPUBufferMapAsyncStatus status, void* userdata);
         static void ForwardFenceCompletedValue(WGPUFenceCompletionStatus status, void* userdata);
+        static void ForwardFenceOnCompletion(WGPUFenceCompletionStatus status, void* userdata);
 
         // Error callbacks
         void OnUncapturedError(WGPUErrorType type, const char* message);
@@ -87,6 +94,8 @@
         void OnBufferMapAsyncCallback(WGPUBufferMapAsyncStatus status, MapUserdata* userdata);
         void OnFenceCompletedValueUpdated(WGPUFenceCompletionStatus status,
                                           FenceCompletionUserdata* userdata);
+        void OnFenceOnCompletion(WGPUFenceCompletionStatus status,
+                                 FenceOnCompletionUserdata* userdata);
 
 #include "dawn_wire/server/ServerPrototypes_autogen.inc"
 
diff --git a/src/dawn_wire/server/ServerFence.cpp b/src/dawn_wire/server/ServerFence.cpp
index 1a4105c..cea561e 100644
--- a/src/dawn_wire/server/ServerFence.cpp
+++ b/src/dawn_wire/server/ServerFence.cpp
@@ -38,4 +38,42 @@
         SerializeCommand(cmd);
     }
 
+    bool Server::DoFenceOnCompletion(ObjectId fenceId, uint64_t value, uint64_t requestSerial) {
+        // The null object isn't valid as `self`
+        if (fenceId == 0) {
+            return false;
+        }
+
+        auto* fence = FenceObjects().Get(fenceId);
+        if (fence == nullptr) {
+            return false;
+        }
+
+        FenceOnCompletionUserdata* userdata = new FenceOnCompletionUserdata;
+        userdata->server = this;
+        userdata->fence = ObjectHandle{fenceId, fence->generation};
+        userdata->requestSerial = requestSerial;
+
+        mProcs.fenceOnCompletion(fence->handle, value, ForwardFenceOnCompletion, userdata);
+        return true;
+    }
+
+    // static
+    void Server::ForwardFenceOnCompletion(WGPUFenceCompletionStatus status, void* userdata) {
+        auto* data = reinterpret_cast<FenceOnCompletionUserdata*>(userdata);
+        data->server->OnFenceOnCompletion(status, data);
+    }
+
+    void Server::OnFenceOnCompletion(WGPUFenceCompletionStatus status,
+                                     FenceOnCompletionUserdata* userdata) {
+        std::unique_ptr<FenceOnCompletionUserdata> data{userdata};
+
+        ReturnFenceOnCompletionCallbackCmd cmd;
+        cmd.fence = data->fence;
+        cmd.requestSerial = data->requestSerial;
+        cmd.status = status;
+
+        SerializeCommand(cmd);
+    }
+
 }}  // namespace dawn_wire::server
diff --git a/src/dawn_wire/server/ServerQueue.cpp b/src/dawn_wire/server/ServerQueue.cpp
index 0c5a6b8..b6d2903 100644
--- a/src/dawn_wire/server/ServerQueue.cpp
+++ b/src/dawn_wire/server/ServerQueue.cpp
@@ -21,7 +21,6 @@
         if (cFence == nullptr) {
             return false;
         }
-
         mProcs.queueSignal(cSelf, cFence, signalValue);
 
         ObjectId fenceId = FenceObjectIdTable().Get(cFence);
diff --git a/src/tests/unittests/wire/WireFenceTests.cpp b/src/tests/unittests/wire/WireFenceTests.cpp
index 1cd5770..29ae5ee 100644
--- a/src/tests/unittests/wire/WireFenceTests.cpp
+++ b/src/tests/unittests/wire/WireFenceTests.cpp
@@ -68,16 +68,17 @@
     }
 
   protected:
-    void DoQueueSignal(uint64_t signalValue) {
+    void DoQueueSignal(uint64_t signalValue,
+                       WGPUFenceCompletionStatus status = WGPUFenceCompletionStatus_Success) {
         wgpuQueueSignal(queue, fence, signalValue);
         EXPECT_CALL(api, QueueSignal(apiQueue, apiFence, signalValue)).Times(1);
 
         // This callback is generated to update the completedValue of the fence
         // on the client
         EXPECT_CALL(api, OnFenceOnCompletionCallback(apiFence, signalValue, _, _))
-            .WillOnce(InvokeWithoutArgs([&]() {
-                api.CallFenceOnCompletionCallback(apiFence, WGPUFenceCompletionStatus_Success);
-            }));
+            .WillOnce(
+                InvokeWithoutArgs([=]() { api.CallFenceOnCompletionCallback(apiFence, status); }))
+            .RetiresOnSaturation();
     }
 
     // A successfully created fence
@@ -88,78 +89,57 @@
 // Check that signaling a fence succeeds
 TEST_F(WireFenceTests, QueueSignalSuccess) {
     DoQueueSignal(2u);
+    FlushClient();
+    FlushServer();
+
+    EXPECT_EQ(wgpuFenceGetCompletedValue(fence), 2u);
+}
+
+// Check that signaling a fence twice succeeds
+TEST_F(WireFenceTests, QueueSignalIncreasing) {
+    DoQueueSignal(2u);
     DoQueueSignal(3u);
     FlushClient();
     FlushServer();
+
+    EXPECT_EQ(wgpuFenceGetCompletedValue(fence), 3u);
 }
 
-// Errors should be generated when signaling a value less
-// than or equal to the current signaled value
+// Check that an error in queue signal does not update the completed value.
 TEST_F(WireFenceTests, QueueSignalValidationError) {
-    wgpuQueueSignal(queue, fence, 0u);  // Error
-    EXPECT_CALL(api, DeviceInjectError(apiDevice, WGPUErrorType_Validation, ValidStringMessage()))
-        .Times(1);
+    DoQueueSignal(2u);
+    DoQueueSignal(1u, WGPUFenceCompletionStatus_Error);
     FlushClient();
+    FlushServer();
 
-    wgpuQueueSignal(queue, fence, 1u);  // Error
-    EXPECT_CALL(api, DeviceInjectError(apiDevice, WGPUErrorType_Validation, ValidStringMessage()))
-        .Times(1);
-    FlushClient();
-
-    DoQueueSignal(4u);  // Success
-    FlushClient();
-
-    wgpuQueueSignal(queue, fence, 3u);  // Error
-    EXPECT_CALL(api, DeviceInjectError(apiDevice, WGPUErrorType_Validation, ValidStringMessage()))
-        .Times(1);
-    FlushClient();
+    // Value should stay at 2 and not be updated to 1.
+    EXPECT_EQ(wgpuFenceGetCompletedValue(fence), 2u);
 }
 
-// Check that callbacks are immediately called if the fence is already finished
-TEST_F(WireFenceTests, OnCompletionImmediate) {
-    // Can call on value < (initial) signaled value happens immediately
-    {
-        EXPECT_CALL(*mockFenceOnCompletionCallback, Call(WGPUFenceCompletionStatus_Success, _))
-            .Times(1);
-        wgpuFenceOnCompletion(fence, 0, ToMockFenceOnCompletionCallback, nullptr);
-    }
+// Check that a success in the on completion callback is forwarded to the client.
+TEST_F(WireFenceTests, OnCompletionSuccess) {
+    wgpuFenceOnCompletion(fence, 0, ToMockFenceOnCompletionCallback, nullptr);
+    EXPECT_CALL(api, OnFenceOnCompletionCallback(apiFence, 0u, _, _))
+        .WillOnce(InvokeWithoutArgs([&]() {
+            api.CallFenceOnCompletionCallback(apiFence, WGPUFenceCompletionStatus_Success);
+        }));
+    FlushClient();
 
-    // Can call on value == (initial) signaled value happens immediately
-    {
-        EXPECT_CALL(*mockFenceOnCompletionCallback, Call(WGPUFenceCompletionStatus_Success, _))
-            .Times(1);
-        wgpuFenceOnCompletion(fence, 1, ToMockFenceOnCompletionCallback, nullptr);
-    }
+    EXPECT_CALL(*mockFenceOnCompletionCallback, Call(WGPUFenceCompletionStatus_Success, _))
+        .Times(1);
+    FlushServer();
 }
 
-// Check that all passed client completion callbacks are called
-TEST_F(WireFenceTests, OnCompletionMultiple) {
-    DoQueueSignal(3u);
-    DoQueueSignal(6u);
-
-    // Add callbacks in a non-monotonic order. They should still be called
-    // in order of increasing fence value.
-    // Add multiple callbacks for the same value.
-    wgpuFenceOnCompletion(fence, 6, ToMockFenceOnCompletionCallback, this + 0);
-    wgpuFenceOnCompletion(fence, 2, ToMockFenceOnCompletionCallback, this + 1);
-    wgpuFenceOnCompletion(fence, 3, ToMockFenceOnCompletionCallback, this + 2);
-    wgpuFenceOnCompletion(fence, 2, ToMockFenceOnCompletionCallback, this + 3);
-
-    Sequence s1, s2;
-    EXPECT_CALL(*mockFenceOnCompletionCallback, Call(WGPUFenceCompletionStatus_Success, this + 1))
-        .Times(1)
-        .InSequence(s1);
-    EXPECT_CALL(*mockFenceOnCompletionCallback, Call(WGPUFenceCompletionStatus_Success, this + 3))
-        .Times(1)
-        .InSequence(s2);
-    EXPECT_CALL(*mockFenceOnCompletionCallback, Call(WGPUFenceCompletionStatus_Success, this + 2))
-        .Times(1)
-        .InSequence(s1, s2);
-    EXPECT_CALL(*mockFenceOnCompletionCallback, Call(WGPUFenceCompletionStatus_Success, this + 0))
-        .Times(1)
-        .InSequence(s1, s2);
-
+// Check that an error in the on completion callback is forwarded to the client.
+TEST_F(WireFenceTests, OnCompletionError) {
+    wgpuFenceOnCompletion(fence, 0, ToMockFenceOnCompletionCallback, nullptr);
+    EXPECT_CALL(api, OnFenceOnCompletionCallback(apiFence, 0u, _, _))
+        .WillOnce(InvokeWithoutArgs([&]() {
+            api.CallFenceOnCompletionCallback(apiFence, WGPUFenceCompletionStatus_Error);
+        }));
     FlushClient();
+
+    EXPECT_CALL(*mockFenceOnCompletionCallback, Call(WGPUFenceCompletionStatus_Error, _)).Times(1);
     FlushServer();
 }
 
@@ -175,19 +155,6 @@
         .Times(3);
 }
 
-// Errors should be generated when waiting on a value greater
-// than the last signaled value
-TEST_F(WireFenceTests, OnCompletionValidationError) {
-    EXPECT_CALL(*mockFenceOnCompletionCallback, Call(WGPUFenceCompletionStatus_Error, this + 0))
-        .Times(1);
-
-    wgpuFenceOnCompletion(fence, 2u, ToMockFenceOnCompletionCallback, this + 0);
-
-    EXPECT_CALL(api, DeviceInjectError(apiDevice, WGPUErrorType_Validation, ValidStringMessage()))
-        .Times(1);
-    FlushClient();
-}
-
 // Check that the fence completed value is initialized
 TEST_F(WireFenceTests, GetCompletedValueInitialization) {
     EXPECT_EQ(wgpuFenceGetCompletedValue(fence), 1u);
@@ -202,6 +169,26 @@
     EXPECT_EQ(wgpuFenceGetCompletedValue(fence), 3u);
 }
 
+// Check that the fence completed value updates after signaling the fence
+TEST_F(WireFenceTests, GetCompletedValueUpdateInCallback) {
+    // Signal the fence
+    DoQueueSignal(3u);
+
+    // Register the callback
+    wgpuFenceOnCompletion(fence, 3u, ToMockFenceOnCompletionCallback, this);
+    EXPECT_CALL(api, OnFenceOnCompletionCallback(apiFence, 3u, _, _))
+        .WillOnce(InvokeWithoutArgs([&]() {
+            api.CallFenceOnCompletionCallback(apiFence, WGPUFenceCompletionStatus_Success);
+        }))
+        .RetiresOnSaturation();
+
+    FlushClient();
+
+    EXPECT_CALL(*mockFenceOnCompletionCallback, Call(WGPUFenceCompletionStatus_Success, this))
+        .WillOnce(InvokeWithoutArgs([&]() { EXPECT_EQ(wgpuFenceGetCompletedValue(fence), 3u); }));
+    FlushServer();
+}
+
 // Check that the fence completed value does not update without a flush
 TEST_F(WireFenceTests, GetCompletedValueNoUpdate) {
     wgpuQueueSignal(queue, fence, 3u);