--- a/services/fxaccounts/FxAccounts.jsm
+++ b/services/fxaccounts/FxAccounts.jsm
@@ -39,16 +39,17 @@ XPCOMUtils.defineLazyModuleGetter(this, 
 
 // All properties exposed by the public FxAccounts API.
 var publicProperties = [
   "accountStatus",
   "checkVerificationStatus",
   "getAccountsClient",
   "getAssertion",
   "getDeviceId",
+  "getDeviceList",
   "getKeys",
   "getOAuthToken",
   "getProfileCache",
   "getSignedInUser",
   "getSignedInUserProfile",
   "handleDeviceDisconnection",
   "invalidateCertificate",
   "loadAndPoll",
@@ -669,16 +670,21 @@ FxAccountsInternal.prototype = {
           return data.deviceId;
         }
 
         // Without a signed-in user, there can be no device id.
         return null;
       });
   },
 
+  async getDeviceList() {
+    let accountData = await this._getVerifiedAccountOrReject();
+    return this.fxAccountsClient.getDeviceList(accountData.sessionToken);
+  },
+
   /**
    * Resend the verification email fot the currently signed-in user.
    *
    */
   resendVerificationEmail: function resendVerificationEmail() {
     let currentState = this.currentAccountState;
     return this.getSignedInUser().then(data => {
       // If the caller is asking for verification to be re-sent, and there is
@@ -1438,27 +1444,28 @@ FxAccountsInternal.prototype = {
     if (existing) {
       // background destroy.
       this._destroyOAuthToken(existing).catch(err => {
         log.warn("FxA failed to revoke a cached token", err);
       });
     }
    }),
 
-  _getVerifiedAccountOrReject: Task.async(function* () {
-    let data = yield this.currentAccountState.getUserAccountData();
+  async _getVerifiedAccountOrReject() {
+    let data = await this.currentAccountState.getUserAccountData();
     if (!data) {
       // No signed-in user
       throw this._error(ERROR_NO_ACCOUNT);
     }
     if (!this.isUserEmailVerified(data)) {
       // Signed-in user has not verified email
       throw this._error(ERROR_UNVERIFIED_ACCOUNT);
     }
-  }),
+    return data;
+  },
 
   /*
    * Coerce an error into one of the general error cases:
    *          NETWORK_ERROR
    *          AUTH_ERROR
    *          UNKNOWN_ERROR
    *
    * These errors will pass through:

--- a/services/sync/modules/engines/clients.js
+++ b/services/sync/modules/engines/clients.js
@@ -75,23 +75,25 @@ Utils.deferGetSet(ClientsRec,
                    "fxaDeviceId"]);
 
 
 this.ClientEngine = function ClientEngine(service) {
   SyncEngine.call(this, "Clients", service);
 
   // Reset the last sync timestamp on every startup so that we fetch all clients
   this.resetLastSync();
+  this.fxAccounts = fxAccounts;
 }
 ClientEngine.prototype = {
   __proto__: SyncEngine.prototype,
   _storeObj: ClientStore,
   _recordObj: ClientsRec,
   _trackerObj: ClientsTracker,
   allowSkippedRecord: false,
+  _knownStaleFxADeviceIds: null,
 
   // Always sync client data as it controls other sync behavior
   get enabled() {
     return true;
   },
 
   get lastRecordUpload() {
     return Svc.Prefs.get(this.name + ".lastRecordUpload", 0);
@@ -184,17 +186,17 @@ ClientEngine.prototype = {
     // the device before syncing, so we don't need to update the registration
     // in this case.
     Svc.Prefs.set("client.name", name);
     return name;
   },
   set localName(value) {
     Svc.Prefs.set("client.name", value);
     // Update the registration in the background.
-    fxAccounts.updateDeviceRegistration().catch(error => {
+    this.fxAccounts.updateDeviceRegistration().catch(error => {
       this._log.warn("failed to update fxa device registration", error);
     });
   },
 
   get localType() {
     return Utils.getDeviceType();
   },
   set localType(value) {
@@ -286,31 +288,53 @@ ClientEngine.prototype = {
   },
 
   _removeClientCommands(clientId) {
     const allCommands = this._readCommands();
     delete allCommands[clientId];
     this._saveCommands(allCommands);
   },
 
-  _syncStartup: function _syncStartup() {
+  // We assume that clients not present in the FxA Device Manager list have been
+  // disconnected and so are stale
+  _refreshKnownStaleClients() {
+    this._log.debug('Refreshing the known stale clients list');
+    let localClients = Object.values(this._store._remoteClients)
+                             .filter(client => client.fxaDeviceId) // iOS client records don't have fxaDeviceId
+                             .map(client => client.fxaDeviceId);
+    let fxaClients;
+    try {
+      fxaClients = Async.promiseSpinningly(this.fxAccounts.getDeviceList()).map(device => device.id);
+    } catch (ex) {
+      this._log.error('Could not retrieve the FxA device list', ex);
+      this._knownStaleFxADeviceIds = [];
+      return;
+    }
+    this._knownStaleFxADeviceIds = Utils.arraySub(localClients, fxaClients);
+  },
+
+  _syncStartup() {
     // Reupload new client record periodically.
     if (Date.now() / 1000 - this.lastRecordUpload > CLIENTS_TTL_REFRESH) {
       this._tracker.addChangedID(this.localID);
       this.lastRecordUpload = Date.now() / 1000;
     }
     SyncEngine.prototype._syncStartup.call(this);
   },
 
   _processIncoming() {
     // Fetch all records from the server.
     this.lastSync = 0;
     this._incomingClients = {};
     try {
       SyncEngine.prototype._processIncoming.call(this);
+      // Refresh the known stale clients list once per browser restart
+      if (!this._knownStaleFxADeviceIds) {
+        this._refreshKnownStaleClients();
+      }
       // Since clients are synced unconditionally, any records in the local store
       // that don't exist on the server must be for disconnected clients. Remove
       // them, so that we don't upload records with commands for clients that will
       // 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}`);
@@ -323,16 +347,20 @@ ClientEngine.prototype = {
       // (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 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)) {
           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;
@@ -411,17 +439,17 @@ ClientEngine.prototype = {
   _notifyCollectionChanged(ids) {
     const message = {
       version: 1,
       command: "sync:collection_changed",
       data: {
         collections: ["clients"]
       }
     };
-    fxAccounts.notifyDevices(ids, message, NOTIFY_TAB_SENT_TTL_SECS);
+    this.fxAccounts.notifyDevices(ids, message, NOTIFY_TAB_SENT_TTL_SECS);
   },
 
   _syncFinish() {
     // Record histograms for our device types, and also write them to a pref
     // so non-histogram telemetry (eg, UITelemetry) and the sync scheduler
     // has easy access to them, and so they are accurate even before we've
     // successfully synced the first time after startup.
     for (let [deviceType, count] of this.deviceTypes) {
@@ -466,16 +494,17 @@ ClientEngine.prototype = {
 
   // Treat reset the same as wiping for locally cached clients
   _resetClient() {
     this._wipeClient();
   },
 
   _wipeClient: function _wipeClient() {
     SyncEngine.prototype._resetClient.call(this);
+    this._knownStaleFxADeviceIds = null;
     delete this.localCommands;
     this._store.wipe();
     const logRemoveError = err => this._log.warn("Could not delete json file", err);
     Async.promiseSpinningly(
       Utils.jsonRemove("commands", this).catch(logRemoveError)
         .then(Utils.jsonRemove("commands-syncing", this).catch(logRemoveError))
     );
   },
@@ -803,17 +832,17 @@ ClientStore.prototype = {
 
     const commandsChanges = this.engine._currentlySyncingCommands ?
                             this.engine._currentlySyncingCommands[id] :
                             [];
 
     // Package the individual components into a record for the local client
     if (id == this.engine.localID) {
       let cb = Async.makeSpinningCallback();
-      fxAccounts.getDeviceId().then(id => cb(null, id), cb);
+      this.engine.fxAccounts.getDeviceId().then(id => cb(null, id), cb);
       try {
         record.fxaDeviceId = cb.wait();
       } catch (error) {
         this._log.warn("failed to get fxa device id", error);
       }
       record.name = this.engine.localName;
       record.type = this.engine.localType;
       record.version = Services.appinfo.version;

--- a/services/sync/tests/unit/test_clients_engine.js
+++ b/services/sync/tests/unit/test_clients_engine.js
@@ -814,16 +814,81 @@ add_task(async function test_command_syn
       let collection = server.getCollection("foo", "clients");
       collection.remove(remoteId);
     } finally {
       await promiseStopServer(server);
     }
   }
 });
 
+add_task(async function test_clients_not_in_fxa_list() {
+  _("Ensure that clients not in the FxA devices list are marked as stale.");
+
+  engine._store.wipe();
+  generateNewKeys(Service.collectionKeys);
+
+  let contents = {
+    meta: {global: {engines: {clients: {version: engine.version,
+                                        syncID: engine.syncID}}}},
+    clients: {},
+    crypto: {}
+  };
+  let server   = serverForUsers({"foo": "password"}, contents);
+  await SyncTestingInfrastructure(server);
+
+  let user     = server.user("foo");
+  let remoteId = Utils.makeGUID();
+  let remoteId2 = 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: remoteId,
+    protocols: ["1.5"],
+  }), Date.now() / 1000));
+  server.insertWBO("foo", "clients", new ServerWBO(remoteId2, encryptPayload({
+    id: remoteId2,
+    name: "Remote client 2",
+    type: "desktop",
+    commands: [],
+    version: "48",
+    fxaDeviceId: remoteId2,
+    protocols: ["1.5"],
+  }), Date.now() / 1000));
+
+  let fxAccounts = engine.fxAccounts;
+  engine.fxAccounts = {
+    getDeviceId() { return fxAccounts.getDeviceId(); },
+    getDeviceList() { return Promise.resolve([{ id: remoteId }]); }
+  };
+
+  try {
+    _("Syncing.");
+    engine._sync();
+
+    ok(!engine._store._remoteClients[remoteId].stale);
+    ok(engine._store._remoteClients[remoteId2].stale);
+
+  } finally {
+    engine.fxAccounts = fxAccounts;
+    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);