diff --git a/dawn.json b/dawn.json
index cb5e83a..5e65d3b 100644
--- a/dawn.json
+++ b/dawn.json
@@ -437,13 +437,6 @@
                 "returns": "command encoder"
             },
             {
-                "name": "create fence",
-                "returns": "fence",
-                "args": [
-                    {"name": "descriptor", "type": "fence descriptor", "annotation": "const*"}
-                ]
-            },
-            {
                 "name": "create input state builder",
                 "returns": "input state builder"
             },
@@ -714,6 +707,13 @@
                     {"name": "fence", "type": "fence"},
                     {"name": "signal value", "type": "uint64_t"}
                 ]
+            },
+            {
+                "name": "create fence",
+                "returns": "fence",
+                "args": [
+                    {"name": "descriptor", "type": "fence descriptor", "annotation": "const*"}
+                ]
             }
         ]
     },
diff --git a/dawn_wire.json b/dawn_wire.json
index defa6e6..debad79 100644
--- a/dawn_wire.json
+++ b/dawn_wire.json
@@ -58,7 +58,7 @@
         ],
         "client_handwritten_commands": [
             "BufferUnmap",
-            "DeviceCreateFence",
+            "QueueCreateFence",
             "FenceGetCompletedValue",
             "QueueSignal"
         ],
diff --git a/src/dawn_native/Device.cpp b/src/dawn_native/Device.cpp
index 5d888b1..0448464 100644
--- a/src/dawn_native/Device.cpp
+++ b/src/dawn_native/Device.cpp
@@ -159,15 +159,6 @@
 
         return result;
     }
-    FenceBase* DeviceBase::CreateFence(const FenceDescriptor* descriptor) {
-        FenceBase* result = nullptr;
-
-        if (ConsumedError(CreateFenceInternal(&result, descriptor))) {
-            return FenceBase::MakeError(this);
-        }
-
-        return result;
-    }
     InputStateBuilder* DeviceBase::CreateInputStateBuilder() {
         return new InputStateBuilder(this);
     }
@@ -302,13 +293,6 @@
         return {};
     }
 
-    MaybeError DeviceBase::CreateFenceInternal(FenceBase** result,
-                                               const FenceDescriptor* descriptor) {
-        DAWN_TRY(ValidateFenceDescriptor(this, descriptor));
-        *result = new FenceBase(this, descriptor);
-        return {};
-    }
-
     MaybeError DeviceBase::CreatePipelineLayoutInternal(
         PipelineLayoutBase** result,
         const PipelineLayoutDescriptor* descriptor) {
diff --git a/src/dawn_native/Device.h b/src/dawn_native/Device.h
index 97e002e..d1c7361 100644
--- a/src/dawn_native/Device.h
+++ b/src/dawn_native/Device.h
@@ -91,7 +91,6 @@
         BufferBase* CreateBuffer(const BufferDescriptor* descriptor);
         CommandEncoderBase* CreateCommandEncoder();
         ComputePipelineBase* CreateComputePipeline(const ComputePipelineDescriptor* descriptor);
-        FenceBase* CreateFence(const FenceDescriptor* descriptor);
         InputStateBuilder* CreateInputStateBuilder();
         PipelineLayoutBase* CreatePipelineLayout(const PipelineLayoutDescriptor* descriptor);
         QueueBase* CreateQueue();
@@ -158,7 +157,6 @@
         MaybeError CreateBufferInternal(BufferBase** result, const BufferDescriptor* descriptor);
         MaybeError CreateComputePipelineInternal(ComputePipelineBase** result,
                                                  const ComputePipelineDescriptor* descriptor);
-        MaybeError CreateFenceInternal(FenceBase** result, const FenceDescriptor* descriptor);
         MaybeError CreatePipelineLayoutInternal(PipelineLayoutBase** result,
                                                 const PipelineLayoutDescriptor* descriptor);
         MaybeError CreateQueueInternal(QueueBase** result);
diff --git a/src/dawn_native/Fence.cpp b/src/dawn_native/Fence.cpp
index 4ab4c7b..49919bd 100644
--- a/src/dawn_native/Fence.cpp
+++ b/src/dawn_native/Fence.cpp
@@ -16,13 +16,14 @@
 
 #include "common/Assert.h"
 #include "dawn_native/Device.h"
+#include "dawn_native/Queue.h"
 #include "dawn_native/ValidationUtils_autogen.h"
 
 #include <utility>
 
 namespace dawn_native {
 
-    MaybeError ValidateFenceDescriptor(DeviceBase*, const FenceDescriptor* descriptor) {
+    MaybeError ValidateFenceDescriptor(const FenceDescriptor* descriptor) {
         if (descriptor->nextInChain != nullptr) {
             return DAWN_VALIDATION_ERROR("nextInChain must be nullptr");
         }
@@ -32,10 +33,11 @@
 
     // Fence
 
-    FenceBase::FenceBase(DeviceBase* device, const FenceDescriptor* descriptor)
-        : ObjectBase(device),
+    FenceBase::FenceBase(QueueBase* queue, const FenceDescriptor* descriptor)
+        : ObjectBase(queue->GetDevice()),
           mSignalValue(descriptor->initialValue),
-          mCompletedValue(descriptor->initialValue) {
+          mCompletedValue(descriptor->initialValue),
+          mQueue(queue) {
     }
 
     FenceBase::FenceBase(DeviceBase* device, ObjectBase::ErrorTag tag) : ObjectBase(device, tag) {
@@ -86,6 +88,11 @@
         return mSignalValue;
     }
 
+    const QueueBase* FenceBase::GetQueue() const {
+        ASSERT(!IsError());
+        return mQueue.Get();
+    }
+
     void FenceBase::SetSignaledValue(uint64_t signalValue) {
         ASSERT(!IsError());
         ASSERT(signalValue > mSignalValue);
diff --git a/src/dawn_native/Fence.h b/src/dawn_native/Fence.h
index 0b1c7d9..da9fbb5 100644
--- a/src/dawn_native/Fence.h
+++ b/src/dawn_native/Fence.h
@@ -26,16 +26,17 @@
 
 namespace dawn_native {
 
-    MaybeError ValidateFenceDescriptor(DeviceBase*, const FenceDescriptor* descriptor);
+    MaybeError ValidateFenceDescriptor(const FenceDescriptor* descriptor);
 
     class FenceBase : public ObjectBase {
       public:
-        FenceBase(DeviceBase* device, const FenceDescriptor* descriptor);
+        FenceBase(QueueBase* queue, const FenceDescriptor* descriptor);
         ~FenceBase();
 
         static FenceBase* MakeError(DeviceBase* device);
 
         uint64_t GetSignaledValue() const;
+        const QueueBase* GetQueue() const;
 
         // Dawn API
         uint64_t GetCompletedValue() const;
@@ -61,6 +62,7 @@
 
         uint64_t mSignalValue;
         uint64_t mCompletedValue;
+        Ref<QueueBase> mQueue;
         SerialMap<OnCompletionData> mRequests;
     };
 
diff --git a/src/dawn_native/Queue.cpp b/src/dawn_native/Queue.cpp
index bd4f43b..eb483aa 100644
--- a/src/dawn_native/Queue.cpp
+++ b/src/dawn_native/Queue.cpp
@@ -47,6 +47,14 @@
         GetDevice()->GetFenceSignalTracker()->UpdateFenceOnComplete(fence, signalValue);
     }
 
+    FenceBase* QueueBase::CreateFence(const FenceDescriptor* descriptor) {
+        if (GetDevice()->ConsumedError(ValidateCreateFence(descriptor))) {
+            return FenceBase::MakeError(GetDevice());
+        }
+
+        return new FenceBase(this, descriptor);
+    }
+
     MaybeError QueueBase::ValidateSubmit(uint32_t commandCount,
                                          CommandBufferBase* const* commands) {
         DAWN_TRY(GetDevice()->ValidateObject(this));
@@ -86,10 +94,21 @@
         DAWN_TRY(GetDevice()->ValidateObject(this));
         DAWN_TRY(GetDevice()->ValidateObject(fence));
 
+        if (fence->GetQueue() != this) {
+            return DAWN_VALIDATION_ERROR(
+                "Fence must be signaled on the queue on which it was created.");
+        }
         if (signalValue <= fence->GetSignaledValue()) {
             return DAWN_VALIDATION_ERROR("Signal value less than or equal to fence signaled value");
         }
         return {};
     }
 
+    MaybeError QueueBase::ValidateCreateFence(const FenceDescriptor* descriptor) {
+        DAWN_TRY(GetDevice()->ValidateObject(this));
+        DAWN_TRY(ValidateFenceDescriptor(descriptor));
+
+        return {};
+    }
+
 }  // namespace dawn_native
diff --git a/src/dawn_native/Queue.h b/src/dawn_native/Queue.h
index 3a31367..3da2f02 100644
--- a/src/dawn_native/Queue.h
+++ b/src/dawn_native/Queue.h
@@ -31,12 +31,14 @@
         // Dawn API
         void Submit(uint32_t commandCount, CommandBufferBase* const* commands);
         void Signal(FenceBase* fence, uint64_t signalValue);
+        FenceBase* CreateFence(const FenceDescriptor* descriptor);
 
       private:
         virtual void SubmitImpl(uint32_t commandCount, CommandBufferBase* const* commands) = 0;
 
         MaybeError ValidateSubmit(uint32_t commandCount, CommandBufferBase* const* commands);
         MaybeError ValidateSignal(const FenceBase* fence, uint64_t signalValue);
+        MaybeError ValidateCreateFence(const FenceDescriptor* descriptor);
     };
 
 }  // namespace dawn_native
diff --git a/src/dawn_wire/client/ApiProcs.cpp b/src/dawn_wire/client/ApiProcs.cpp
index b19cc50..60ffa5b 100644
--- a/src/dawn_wire/client/ApiProcs.cpp
+++ b/src/dawn_wire/client/ApiProcs.cpp
@@ -133,10 +133,11 @@
         cmd.Serialize(allocatedBuffer, *buffer->device->GetClient());
     }
 
-    dawnFence ClientDeviceCreateFence(dawnDevice cSelf, dawnFenceDescriptor const* descriptor) {
-        Device* device = reinterpret_cast<Device*>(cSelf);
+    dawnFence ClientQueueCreateFence(dawnQueue cSelf, dawnFenceDescriptor const* descriptor) {
+        Queue* queue = reinterpret_cast<Queue*>(cSelf);
+        Device* device = queue->device;
 
-        DeviceCreateFenceCmd cmd;
+        QueueCreateFenceCmd cmd;
         cmd.self = cSelf;
         auto* allocation = device->GetClient()->FenceAllocator().New(device);
         cmd.result = ObjectHandle{allocation->object->id, allocation->serial};
@@ -149,6 +150,7 @@
         dawnFence cFence = reinterpret_cast<dawnFence>(allocation->object.get());
 
         Fence* fence = reinterpret_cast<Fence*>(cFence);
+        fence->queue = queue;
         fence->signaledValue = descriptor->initialValue;
         fence->completedValue = descriptor->initialValue;
         return cFence;
@@ -156,6 +158,12 @@
 
     void ClientQueueSignal(dawnQueue cQueue, dawnFence cFence, uint64_t signalValue) {
         Fence* fence = reinterpret_cast<Fence*>(cFence);
+        Queue* queue = reinterpret_cast<Queue*>(cQueue);
+        if (fence->queue != queue) {
+            fence->device->HandleError(
+                "Fence must be signaled on the queue on which it was created.");
+            return;
+        }
         if (signalValue <= fence->signaledValue) {
             fence->device->HandleError("Fence value less than or equal to signaled value");
             return;
diff --git a/src/dawn_wire/client/Fence.h b/src/dawn_wire/client/Fence.h
index dd17b7c..ecfede2 100644
--- a/src/dawn_wire/client/Fence.h
+++ b/src/dawn_wire/client/Fence.h
@@ -22,6 +22,7 @@
 
 namespace dawn_wire { namespace client {
 
+    struct Queue;
     struct Fence : ObjectBase {
         using ObjectBase::ObjectBase;
 
@@ -32,6 +33,7 @@
             dawnFenceOnCompletionCallback completionCallback = nullptr;
             dawnCallbackUserdata userdata = 0;
         };
+        Queue* queue = nullptr;
         uint64_t signaledValue = 0;
         uint64_t completedValue = 0;
         SerialMap<OnCompletionData> requests;
diff --git a/src/tests/end2end/FenceTests.cpp b/src/tests/end2end/FenceTests.cpp
index 9e6d484..e032da8 100644
--- a/src/tests/end2end/FenceTests.cpp
+++ b/src/tests/end2end/FenceTests.cpp
@@ -69,7 +69,7 @@
 TEST_P(FenceTests, SimpleSignal) {
     dawn::FenceDescriptor descriptor;
     descriptor.initialValue = 1u;
-    dawn::Fence fence = device.CreateFence(&descriptor);
+    dawn::Fence fence = queue.CreateFence(&descriptor);
 
     // Completed value starts at initial value
     EXPECT_EQ(fence.GetCompletedValue(), 1u);
@@ -85,7 +85,7 @@
 TEST_P(FenceTests, OnCompletionOrdering) {
     dawn::FenceDescriptor descriptor;
     descriptor.initialValue = 0u;
-    dawn::Fence fence = device.CreateFence(&descriptor);
+    dawn::Fence fence = queue.CreateFence(&descriptor);
 
     queue.Signal(fence, 4);
 
@@ -126,7 +126,7 @@
 TEST_P(FenceTests, MultipleSignalOnCompletion) {
     dawn::FenceDescriptor descriptor;
     descriptor.initialValue = 0u;
-    dawn::Fence fence = device.CreateFence(&descriptor);
+    dawn::Fence fence = queue.CreateFence(&descriptor);
 
     queue.Signal(fence, 2);
     queue.Signal(fence, 4);
@@ -144,7 +144,7 @@
 TEST_P(FenceTests, OnCompletionMultipleCallbacks) {
     dawn::FenceDescriptor descriptor;
     descriptor.initialValue = 0u;
-    dawn::Fence fence = device.CreateFence(&descriptor);
+    dawn::Fence fence = queue.CreateFence(&descriptor);
 
     queue.Signal(fence, 4);
 
@@ -182,13 +182,13 @@
 TEST_P(FenceTests, DISABLED_DestroyBeforeOnCompletionEnd) {
     dawn::FenceDescriptor descriptor;
     descriptor.initialValue = 0u;
-    dawn::Fence fence = device.CreateFence(&descriptor);
+    dawn::Fence fence = queue.CreateFence(&descriptor);
 
     // The fence in this block will be deleted when it goes out of scope
     {
         dawn::FenceDescriptor descriptor;
         descriptor.initialValue = 0u;
-        dawn::Fence testFence = device.CreateFence(&descriptor);
+        dawn::Fence testFence = queue.CreateFence(&descriptor);
 
         queue.Signal(testFence, 4);
 
diff --git a/src/tests/end2end/IOSurfaceWrappingTests.cpp b/src/tests/end2end/IOSurfaceWrappingTests.cpp
index 8c41fd3..957e6bc 100644
--- a/src/tests/end2end/IOSurfaceWrappingTests.cpp
+++ b/src/tests/end2end/IOSurfaceWrappingTests.cpp
@@ -351,7 +351,7 @@
         // Maybe it is because the Metal command buffer has been submitted but not "scheduled" yet?
         dawn::FenceDescriptor fenceDescriptor;
         fenceDescriptor.initialValue = 0u;
-        dawn::Fence fence = device.CreateFence(&fenceDescriptor);
+        dawn::Fence fence = queue.CreateFence(&fenceDescriptor);
         queue.Signal(fence, 1);
 
         while (fence.GetCompletedValue() < 1) {
diff --git a/src/tests/unittests/validation/FenceValidationTests.cpp b/src/tests/unittests/validation/FenceValidationTests.cpp
index 5add1bc..c8b49ba 100644
--- a/src/tests/unittests/validation/FenceValidationTests.cpp
+++ b/src/tests/unittests/validation/FenceValidationTests.cpp
@@ -77,7 +77,7 @@
     {
         dawn::FenceDescriptor descriptor;
         descriptor.initialValue = 0;
-        device.CreateFence(&descriptor);
+        queue.CreateFence(&descriptor);
     }
 }
 
@@ -86,7 +86,7 @@
     {
         dawn::FenceDescriptor descriptor;
         descriptor.initialValue = 1;
-        dawn::Fence fence = device.CreateFence(&descriptor);
+        dawn::Fence fence = queue.CreateFence(&descriptor);
         EXPECT_EQ(fence.GetCompletedValue(), 1u);
     }
 }
@@ -96,7 +96,7 @@
 TEST_F(FenceValidationTest, OnCompletionImmediate) {
     dawn::FenceDescriptor descriptor;
     descriptor.initialValue = 1;
-    dawn::Fence fence = device.CreateFence(&descriptor);
+    dawn::Fence fence = queue.CreateFence(&descriptor);
 
     EXPECT_CALL(*mockFenceOnCompletionCallback, Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, 0))
         .Times(1);
@@ -111,7 +111,7 @@
 TEST_F(FenceValidationTest, OnCompletionLargerThanSignaled) {
     dawn::FenceDescriptor descriptor;
     descriptor.initialValue = 1;
-    dawn::Fence fence = device.CreateFence(&descriptor);
+    dawn::Fence fence = queue.CreateFence(&descriptor);
 
     // Cannot signal for values > signaled value
     EXPECT_CALL(*mockFenceOnCompletionCallback, Call(DAWN_FENCE_COMPLETION_STATUS_ERROR, 0))
@@ -130,7 +130,7 @@
 TEST_F(FenceValidationTest, GetCompletedValueInsideCallback) {
     dawn::FenceDescriptor descriptor;
     descriptor.initialValue = 1;
-    dawn::Fence fence = device.CreateFence(&descriptor);
+    dawn::Fence fence = queue.CreateFence(&descriptor);
 
     queue.Signal(fence, 3);
     fence.OnCompletion(2u, ToMockFenceOnCompletionCallback, 0);
@@ -145,7 +145,7 @@
 TEST_F(FenceValidationTest, GetCompletedValueAfterCallback) {
     dawn::FenceDescriptor descriptor;
     descriptor.initialValue = 1;
-    dawn::Fence fence = device.CreateFence(&descriptor);
+    dawn::Fence fence = queue.CreateFence(&descriptor);
 
     queue.Signal(fence, 2);
     fence.OnCompletion(2u, ToMockFenceOnCompletionCallback, 0);
@@ -159,7 +159,7 @@
 TEST_F(FenceValidationTest, SignalError) {
     dawn::FenceDescriptor descriptor;
     descriptor.initialValue = 1;
-    dawn::Fence fence = device.CreateFence(&descriptor);
+    dawn::Fence fence = queue.CreateFence(&descriptor);
 
     // value < fence signaled value
     ASSERT_DEVICE_ERROR(queue.Signal(fence, 0));
@@ -171,7 +171,7 @@
 TEST_F(FenceValidationTest, SignalSuccess) {
     dawn::FenceDescriptor descriptor;
     descriptor.initialValue = 1;
-    dawn::Fence fence = device.CreateFence(&descriptor);
+    dawn::Fence fence = queue.CreateFence(&descriptor);
 
     // Success
     queue.Signal(fence, 2);
@@ -183,3 +183,34 @@
     Flush();
     EXPECT_EQ(fence.GetCompletedValue(), 6u);
 }
+
+// Test it is invalid to signal a fence on a different queue than it was created on
+TEST_F(FenceValidationTest, SignalWrongQueue) {
+    dawn::Queue queue2 = device.CreateQueue();
+
+    dawn::FenceDescriptor descriptor;
+    descriptor.initialValue = 1;
+    dawn::Fence fence = queue.CreateFence(&descriptor);
+
+    ASSERT_DEVICE_ERROR(queue2.Signal(fence, 2));
+}
+
+// Test that signaling a fence on a wrong queue does not update fence signaled value
+TEST_F(FenceValidationTest, SignalWrongQueueDoesNotUpdateValue) {
+    dawn::Queue queue2 = device.CreateQueue();
+
+    dawn::FenceDescriptor descriptor;
+    descriptor.initialValue = 1;
+    dawn::Fence fence = queue.CreateFence(&descriptor);
+
+    ASSERT_DEVICE_ERROR(queue2.Signal(fence, 2));
+
+    // Fence value should be unchanged.
+    Flush();
+    EXPECT_EQ(fence.GetCompletedValue(), 1u);
+
+    // Signaling with 2 on the correct queue should succeed
+    queue.Signal(fence, 2);
+    Flush();
+    EXPECT_EQ(fence.GetCompletedValue(), 2u);
+}
diff --git a/src/tests/unittests/wire/WireFenceTests.cpp b/src/tests/unittests/wire/WireFenceTests.cpp
index 5c8fb88..e324d7c 100644
--- a/src/tests/unittests/wire/WireFenceTests.cpp
+++ b/src/tests/unittests/wire/WireFenceTests.cpp
@@ -56,24 +56,24 @@
         mockFenceOnCompletionCallback = std::make_unique<MockFenceOnCompletionCallback>();
 
         {
+            queue = dawnDeviceCreateQueue(device);
+            apiQueue = api.GetNewQueue();
+            EXPECT_CALL(api, DeviceCreateQueue(apiDevice)).WillOnce(Return(apiQueue));
+            EXPECT_CALL(api, QueueRelease(apiQueue));
+            FlushClient();
+        }
+        {
             dawnFenceDescriptor descriptor;
             descriptor.initialValue = 1;
             descriptor.nextInChain = nullptr;
 
             apiFence = api.GetNewFence();
-            fence = dawnDeviceCreateFence(device, &descriptor);
+            fence = dawnQueueCreateFence(queue, &descriptor);
 
-            EXPECT_CALL(api, DeviceCreateFence(apiDevice, _)).WillOnce(Return(apiFence));
+            EXPECT_CALL(api, QueueCreateFence(apiQueue, _)).WillOnce(Return(apiFence));
             EXPECT_CALL(api, FenceRelease(apiFence));
             FlushClient();
         }
-        {
-            queue = dawnDeviceCreateQueue(device);
-            apiQueue = api.GetNewQueue();
-            EXPECT_CALL(api, DeviceCreateQueue(apiDevice)).WillOnce(Return(apiQueue));
-            EXPECT_CALL(api, QueueRelease(apiQueue));
-            FlushClient();
-        }
     }
 
     void TearDown() override {
@@ -264,3 +264,44 @@
 
     dawnFenceRelease(fence);
 }
+
+// Test that signaling a fence on a wrong queue is invalid
+TEST_F(WireFenceTests, SignalWrongQueue) {
+    dawnQueue queue2 = dawnDeviceCreateQueue(device);
+    dawnQueue apiQueue2 = api.GetNewQueue();
+    EXPECT_CALL(api, DeviceCreateQueue(apiDevice)).WillOnce(Return(apiQueue2));
+    EXPECT_CALL(api, QueueRelease(apiQueue2));
+    FlushClient();
+
+    dawnCallbackUserdata userdata = 1520;
+    dawnDeviceSetErrorCallback(device, ToMockDeviceErrorCallback, userdata);
+
+    EXPECT_CALL(*mockDeviceErrorCallback, Call(_, userdata)).Times(1);
+    dawnQueueSignal(queue2, fence, 2u);  // error
+}
+
+// Test that signaling a fence on a wrong queue does not update fence signaled value
+TEST_F(WireFenceTests, SignalWrongQueueDoesNotUpdateValue) {
+    dawnQueue queue2 = dawnDeviceCreateQueue(device);
+    dawnQueue apiQueue2 = api.GetNewQueue();
+    EXPECT_CALL(api, DeviceCreateQueue(apiDevice)).WillOnce(Return(apiQueue2));
+    EXPECT_CALL(api, QueueRelease(apiQueue2));
+    FlushClient();
+
+    dawnCallbackUserdata userdata = 1024;
+    dawnDeviceSetErrorCallback(device, ToMockDeviceErrorCallback, userdata);
+
+    EXPECT_CALL(*mockDeviceErrorCallback, Call(_, userdata)).Times(1);
+    dawnQueueSignal(queue2, fence, 2u);  // error
+
+    // Fence value should be unchanged.
+    FlushClient();
+    FlushServer();
+    EXPECT_EQ(dawnFenceGetCompletedValue(fence), 1u);
+
+    // Signaling with 2 on the correct queue should succeed
+    DoQueueSignal(2u);  // success
+    FlushClient();
+    FlushServer();
+    EXPECT_EQ(dawnFenceGetCompletedValue(fence), 2u);
+}