--- a/services/sync/modules/engines/clients.js
+++ b/services/sync/modules/engines/clients.js
@@ -305,20 +305,37 @@ ClientEngine.prototype = {
     const allCommands = await this._readCommands();
     delete allCommands[clientId];
     await this._saveCommands(allCommands);
   },
 
   async updateKnownStaleClients() {
     this._log.debug("Updating the known stale clients");
     await this._refreshKnownStaleClients();
-    for (let client of Object.values(this._store._remoteClients)) {
-      if (client.fxaDeviceId && this._knownStaleFxADeviceIds.includes(client.fxaDeviceId)) {
+    let localFxADeviceId = await fxAccounts.getDeviceId();
+    // Process newer records first, so that if we hit a record with a device ID
+    // we've seen before, we can mark it stale immediately.
+    let clientList = Object.values(this._store._remoteClients).sort((a, b) =>
+      b.serverLastModified - a.serverLastModified);
+    let seenDeviceIds = new Set([localFxADeviceId]);
+    for (let client of clientList) {
+      // Clients might not have an `fxaDeviceId` if they fail the FxA
+      // registration process.
+      if (!client.fxaDeviceId) {
+        continue;
+      }
+      if (this._knownStaleFxADeviceIds.includes(client.fxaDeviceId)) {
         this._log.info(`Hiding stale client ${client.id} - in known stale clients list`);
         client.stale = true;
+      } else if (seenDeviceIds.has(client.fxaDeviceId)) {
+        this._log.info(`Hiding stale client ${client.id}` +
+                       ` - duplicate device id ${client.fxaDeviceId}`);
+        client.stale = true;
+      } else {
+        seenDeviceIds.add(client.fxaDeviceId);
       }
     }
   },
 
   // We assume that clients not present in the FxA Device Manager list have been
   // disconnected and so are stale
   async _refreshKnownStaleClients() {
     this._log.debug("Refreshing the known stale clients list");
@@ -364,39 +381,54 @@ ClientEngine.prototype = {
       // never see them. We also do this to filter out stale clients from the
       // tabs collection, since showing their list of tabs is confusing.
       for (let id in this._store._remoteClients) {
         if (!this._incomingClients[id]) {
           this._log.info(`Removing local state for deleted client ${id}`);
           await this._removeRemoteClient(id);
         }
       }
+      let localFxADeviceId = await fxAccounts.getDeviceId();
       // Bug 1264498: Mobile clients don't remove themselves from the clients
       // collection when the user disconnects Sync, so we mark as stale clients
       // with the same name that haven't synced in over a week.
       // (Note we can't simply delete them, or we re-apply them next sync - see
       // bug 1287687)
       delete this._incomingClients[this.localID];
       let names = new Set([this.localName]);
-      for (let [id, serverLastModified] of Object.entries(this._incomingClients)) {
+      let seenDeviceIds = new Set([localFxADeviceId]);
+      let idToLastModifiedList = Object.entries(this._incomingClients)
+                                 .sort((a, b) => b[1] - a[1]);
+      for (let [id, serverLastModified] of idToLastModifiedList) {
         let record = this._store._remoteClients[id];
         // stash the server last-modified time on the record.
         record.serverLastModified = serverLastModified;
         if (record.fxaDeviceId && this._knownStaleFxADeviceIds.includes(record.fxaDeviceId)) {
           this._log.info(`Hiding stale client ${id} - in known stale clients list`);
           record.stale = true;
         }
         if (!names.has(record.name)) {
+          if (record.fxaDeviceId) {
+            seenDeviceIds.add(record.fxaDeviceId);
+          }
           names.add(record.name);
           continue;
         }
         let remoteAge = AsyncResource.serverTime - this._incomingClients[id];
         if (remoteAge > STALE_CLIENT_REMOTE_AGE) {
           this._log.info(`Hiding stale client ${id} with age ${remoteAge}`);
           record.stale = true;
+          continue;
+        }
+        if (record.fxaDeviceId && seenDeviceIds.has(record.fxaDeviceId)) {
+          this._log.info(`Hiding stale client ${record.id}` +
+                         ` - duplicate device id ${record.fxaDeviceId}`);
+          record.stale = true;
+        } else if (record.fxaDeviceId) {
+          seenDeviceIds.add(record.fxaDeviceId);
         }
       }
     } finally {
       this._incomingClients = null;
     }
   },
 
   async _uploadOutgoing() {

--- a/services/sync/tests/unit/test_clients_engine.js
+++ b/services/sync/tests/unit/test_clients_engine.js
@@ -865,16 +865,78 @@ add_task(async function test_clients_not
       let collection = server.getCollection("foo", "clients");
       collection.remove(remoteId);
     } finally {
       await promiseStopServer(server);
     }
   }
 });
 
+
+add_task(async function test_dupe_device_ids() {
+  _("Ensure that we mark devices with duplicate fxaDeviceIds but older lastModified as stale.");
+
+  await engine._store.wipe();
+  await generateNewKeys(Service.collectionKeys);
+
+  let server   = await serverForFoo(engine);
+  await SyncTestingInfrastructure(server);
+
+  let remoteId = Utils.makeGUID();
+  let remoteId2 = Utils.makeGUID();
+  let remoteDeviceId = Utils.makeGUID();
+
+  _("Create remote client records");
+  server.insertWBO("foo", "clients", new ServerWBO(remoteId, encryptPayload({
+    id: remoteId,
+    name: "Remote client",
+    type: "desktop",
+    commands: [],
+    version: "48",
+    fxaDeviceId: remoteDeviceId,
+    protocols: ["1.5"],
+  }), Date.now() / 1000 - 30000));
+  server.insertWBO("foo", "clients", new ServerWBO(remoteId2, encryptPayload({
+    id: remoteId2,
+    name: "Remote client",
+    type: "desktop",
+    commands: [],
+    version: "48",
+    fxaDeviceId: remoteDeviceId,
+    protocols: ["1.5"],
+  }), Date.now() / 1000));
+
+  let fxAccounts = engine.fxAccounts;
+  engine.fxAccounts = {
+    notifyDevices() { return Promise.resolve(true); },
+    getDeviceId() { return fxAccounts.getDeviceId(); },
+    getDeviceList() { return Promise.resolve([{ id: remoteDeviceId }]); }
+  };
+
+  try {
+    _("Syncing.");
+    await syncClientsEngine(server);
+
+    ok(engine._store._remoteClients[remoteId].stale);
+    ok(!engine._store._remoteClients[remoteId2].stale);
+
+  } finally {
+    engine.fxAccounts = fxAccounts;
+    await cleanup();
+
+    try {
+      let collection = server.getCollection("foo", "clients");
+      collection.remove(remoteId);
+    } finally {
+      await promiseStopServer(server);
+    }
+  }
+});
+
+
 add_task(async function test_send_uri_to_client_for_display() {
   _("Ensure sendURIToClientForDisplay() sends command properly.");
 
   let tracker = engine._tracker;
   let store = engine._store;
 
   let remoteId = Utils.makeGUID();
   let rec = new ClientsRec("clients", remoteId);