--- a/services/sync/modules/SyncedTabs.jsm
+++ b/services/sync/modules/SyncedTabs.jsm
@@ -116,16 +116,19 @@ let SyncedTabsInternal = {
 
     let engine = Weave.Service.engineManager.get("tabs");
 
     let seenURLs = new Set();
     let parentIndex = 0;
     let ntabs = 0;
 
     for (let [guid, client] in Iterator(engine.getAllClients())) {
+      if (!Weave.Service.clientsEngine.remoteClientExists(client.id)) {
+        continue;
+      }
       let clientRepr = yield this._makeClient(client);
       log.debug("Processing client", clientRepr);
 
       for (let tab of client.tabs) {
         let url = tab.urlHistory[0];
         log.debug("remote tab", url);
         // Note there are some issues with tracking "seen" tabs, including:
         // * We really can't return the entire urlHistory record as we are

--- a/services/sync/modules/engines/clients.js
+++ b/services/sync/modules/engines/clients.js
@@ -135,16 +135,20 @@ ClientEngine.prototype = {
 
   get localType() {
     return Utils.getDeviceType();
   },
   set localType(value) {
     Svc.Prefs.set("client.type", value);
   },
 
+  remoteClientExists(id) {
+    return !!this._store._remoteClients[id];
+  },
+
   isMobile: function isMobile(id) {
     if (this._store._remoteClients[id])
       return this._store._remoteClients[id].type == DEVICE_TYPE_MOBILE;
     return false;
   },
 
   _syncStartup: function _syncStartup() {
     // Reupload new client record periodically.

--- a/services/sync/tests/unit/test_syncedtabs.js
+++ b/services/sync/tests/unit/test_syncedtabs.js
@@ -34,16 +34,19 @@ MockTabsEngine.prototype = {
 // A clients engine that doesn't need to be a constructor.
 let MockClientsEngine = {
   isMobile(guid) {
     if (!guid.endsWith("desktop") && !guid.endsWith("mobile")) {
       throw new Error("this module expected guids to end with 'desktop' or 'mobile'");
     }
     return guid.endsWith("mobile");
   },
+  remoteClientExists(id) {
+    return !id.startsWith("guid_stale");
+  },
 }
 
 // Configure Sync with our mock tabs engine and force it to become initialized.
 Services.prefs.setCharPref("services.sync.username", "someone@somewhere.com");
 
 Weave.Service.engineManager.unregister("tabs");
 Weave.Service.engineManager.register(MockTabsEngine);
 Weave.Service.clientsEngine = MockClientsEngine;
@@ -96,16 +99,51 @@ add_task(function* test_clientWithTabs()
   clients.sort((a, b) => { return a.name.localeCompare(b.name);});
   equal(clients[0].tabs.length, 1);
   equal(clients[0].tabs[0].url, "http://foo.com/");
   equal(clients[0].tabs[0].icon, "http://foo.com/favicon");
   // second client has no tabs.
   equal(clients[1].tabs.length, 0);
 });
 
+add_task(function* test_staleClientWithTabs() {
+  yield configureClients({
+    guid_desktop: {
+      clientName: "My Desktop",
+      tabs: [
+      {
+        urlHistory: ["http://foo.com/"],
+        icon: "http://foo.com/favicon",
+      }],
+    },
+    guid_mobile: {
+      clientName: "My Phone",
+      tabs: [],
+    },
+    guid_stale_mobile: {
+      clientName: "My Deleted Phone",
+      tabs: [],
+    },
+    guid_stale_desktop: {
+      clientName: "My Deleted Laptop",
+      tabs: [
+      {
+        urlHistory: ["https://bar.com/"],
+        icon: "https://bar.com/favicon",
+      }],
+    },
+  });
+  let clients = yield SyncedTabs.getTabClients();
+  clients.sort((a, b) => { return a.name.localeCompare(b.name);});
+  equal(clients.length, 2);
+  equal(clients[0].tabs.length, 1);
+  equal(clients[0].tabs[0].url, "http://foo.com/");
+  equal(clients[1].tabs.length, 0);
+});
+
 add_task(function* test_clientWithTabsIconsDisabled() {
   Services.prefs.setBoolPref("services.sync.syncedTabs.showRemoteIcons", false);
   yield configureClients({
     guid_desktop: {
       clientName: "My Desktop",
       tabs: [
       {
         urlHistory: ["http://foo.com/"],