--- a/services/sync/modules/engines/clients.js
+++ b/services/sync/modules/engines/clients.js
@@ -123,22 +123,25 @@ ClientEngine.prototype = {
     }
 
     return stats;
   },
 
   /**
    * Obtain information about device types.
    *
-   * Returns a Map of device types to integer counts.
+   * Returns a Map of device types to integer counts. Guaranteed to include
+   * "desktop" (which will have at least 1 - this device) and "mobile" (which
+   * may have zero) counts. It almost certainly will include only these 2.
    */
   get deviceTypes() {
     let counts = new Map();
 
-    counts.set(this.localType, 1);
+    counts.set(this.localType, 1); // currently this must be DEVICE_TYPE_DESKTOP
+    counts.set(DEVICE_TYPE_MOBILE, 0);
 
     for (let id in this._store._remoteClients) {
       let record = this._store._remoteClients[id];
       if (record.stale) {
         continue; // pretend "stale" records don't exist.
       }
       let type = record.type;
       if (!counts.has(type)) {
@@ -380,26 +383,28 @@ ClientEngine.prototype = {
         collections: ["clients"]
       }
     };
     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) has easy access to them.
+    // 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) {
       let hid;
       let prefName = this.name + ".devices.";
       switch (deviceType) {
-        case "desktop":
+        case DEVICE_TYPE_DESKTOP:
           hid = "WEAVE_DEVICE_COUNT_DESKTOP";
           prefName += "desktop";
           break;
-        case "mobile":
+        case DEVICE_TYPE_MOBILE:
           hid = "WEAVE_DEVICE_COUNT_MOBILE";
           prefName += "mobile";
           break;
         default:
           this._log.warn(`Unexpected deviceType "${deviceType}" recording device telemetry.`);
           continue;
       }
       Services.telemetry.getHistogramById(hid).add(count);

--- a/services/sync/modules/policies.js
+++ b/services/sync/modules/policies.js
@@ -52,16 +52,21 @@ SyncScheduler.prototype = {
     this.activeInterval       = getThrottledIntervalPreference("scheduler.activeInterval");
     this.immediateInterval    = getThrottledIntervalPreference("scheduler.immediateInterval");
     this.eolInterval          = getThrottledIntervalPreference("scheduler.eolInterval");
 
     // A user is non-idle on startup by default.
     this.idle = false;
 
     this.hasIncomingItems = false;
+    // This is the last number of clients we saw when previously updating the
+    // client mode. If this != currentNumClients (obtained from prefs written
+    // by the clients engine) then we need to transition to and from
+    // single and multi-device mode.
+    this.numClientsLastSync = 0;
 
     this.clearSyncTriggers();
   },
 
   // nextSync is in milliseconds, but prefs can't hold that much
   get nextSync() {
     return Svc.Prefs.get("nextSync", 0) * 1000;
   },
@@ -85,21 +90,25 @@ SyncScheduler.prototype = {
 
   get globalScore() {
     return Svc.Prefs.get("globalScore", 0);
   },
   set globalScore(value) {
     Svc.Prefs.set("globalScore", value);
   },
 
+  // The number of clients we have is maintained in preferences via the
+  // clients engine, and only updated after a successsful sync.
   get numClients() {
-    return Svc.Prefs.get("numClients", 0);
+    return Svc.Prefs.get("clients.devices.desktop", 0) +
+           Svc.Prefs.get("clients.devices.mobile", 0);
+
   },
   set numClients(value) {
-    Svc.Prefs.set("numClients", value);
+    throw new Error("Don't set numClients - the clients engine manages it.")
   },
 
   init: function init() {
     this._log.level = Log.Level[Svc.Prefs.get("log.logger.service.main")];
     this.setDefaults();
     Svc.Obs.add("weave:engine:score:updated", this);
     Svc.Obs.add("network:offline-status-changed", this);
     Svc.Obs.add("weave:service:sync:start", this);
@@ -326,26 +335,26 @@ SyncScheduler.prototype = {
       engines[i]._tracker.resetScore();
     }
 
     this._log.trace("Global score updated: " + this.globalScore);
     this.checkSyncStatus();
   },
 
   /**
-   * Process the locally stored clients list to figure out what mode to be in
+   * Query the number of known clients to figure out what mode to be in
    */
   updateClientMode: function updateClientMode() {
     // Nothing to do if it's the same amount
-    let numClients = this.service.clientsEngine.stats.numClients;
-    if (this.numClients == numClients)
+    let numClients = this.numClients;
+    if (numClients == this.numClientsLastSync)
       return;
 
-    this._log.debug("Client count: " + this.numClients + " -> " + numClients);
-    this.numClients = numClients;
+    this._log.debug(`Client count: ${this.numClientsLastSync} -> ${numClients}`);
+    this.numClientsLastSync = numClients;
 
     if (numClients <= 1) {
       this._log.trace("Adjusting syncThreshold to SINGLE_USER_THRESHOLD");
       this.syncThreshold = SINGLE_USER_THRESHOLD;
     } else {
       this._log.trace("Adjusting syncThreshold to MULTI_DEVICE_THRESHOLD");
       this.syncThreshold = MULTI_DEVICE_THRESHOLD;
     }

--- a/services/sync/tests/unit/test_interval_triggers.js
+++ b/services/sync/tests/unit/test_interval_triggers.js
@@ -109,17 +109,17 @@ add_task(async function test_successful_
   do_check_eq(syncSuccesses, 4);
   do_check_true(scheduler.idle);
   do_check_false(scheduler.numClients > 1);
   do_check_true(scheduler.hasIncomingItems);
   do_check_eq(scheduler.syncInterval, scheduler.singleDeviceInterval);
 
   _("Test as long as idle && numClients > 1 our sync interval is idleInterval.");
   // idle == true && numClients > 1 && hasIncomingItems == true
-  Service.clientsEngine._store.create({id: "foo", cleartext: "bar"});
+  Service.clientsEngine._store.create({ id: "foo", cleartext: { name: "bar", type: "mobile" } });
   Service.sync();
   do_check_eq(syncSuccesses, 5);
   do_check_true(scheduler.idle);
   do_check_true(scheduler.numClients > 1);
   do_check_true(scheduler.hasIncomingItems);
   do_check_eq(scheduler.syncInterval, scheduler.idleInterval);
 
   // idle == true && numClients > 1 && hasIncomingItems == false
@@ -213,17 +213,18 @@ add_task(async function test_unsuccessfu
   do_check_eq(syncFailures, 4);
   do_check_true(scheduler.idle);
   do_check_false(scheduler.numClients > 1);
   do_check_true(scheduler.hasIncomingItems);
   do_check_eq(scheduler.syncInterval, scheduler.singleDeviceInterval);
 
   _("Test as long as idle && numClients > 1 our sync interval is idleInterval.");
   // idle == true && numClients > 1 && hasIncomingItems == true
-  Service.clientsEngine._store.create({id: "foo", cleartext: "bar"});
+  Svc.Prefs.set("clients.devices.mobile", 2);
+  scheduler.updateClientMode();
 
   Service.sync();
   do_check_eq(syncFailures, 5);
   do_check_true(scheduler.idle);
   do_check_true(scheduler.numClients > 1);
   do_check_true(scheduler.hasIncomingItems);
   do_check_eq(scheduler.syncInterval, scheduler.idleInterval);
 
@@ -266,17 +267,17 @@ add_task(async function test_back_trigge
   await setUp(server);
 
   // Single device: no sync triggered.
   scheduler.idle = true;
   scheduler.observe(null, "active", Svc.Prefs.get("scheduler.idleTime"));
   do_check_false(scheduler.idle);
 
   // Multiple devices: sync is triggered.
-  clientsEngine._store.create({id: "foo", cleartext: "bar"});
+  Svc.Prefs.set("clients.devices.mobile", 2);
   scheduler.updateClientMode();
 
   let promiseDone = promiseOneObserver("weave:service:sync:finish");
 
   scheduler.idle = true;
   scheduler.observe(null, "active", Svc.Prefs.get("scheduler.idleTime"));
   do_check_false(scheduler.idle);
   await promiseDone;
@@ -304,17 +305,17 @@ add_task(async function test_adjust_inte
   _("Test unsuccessful sync updates client mode & sync intervals");
   // Force a sync fail.
   Svc.Prefs.set("firstSync", "notReady");
 
   do_check_eq(syncFailures, 0);
   do_check_false(scheduler.numClients > 1);
   do_check_eq(scheduler.syncInterval, scheduler.singleDeviceInterval);
 
-  clientsEngine._store.create({id: "foo", cleartext: "bar"});
+  Svc.Prefs.set("clients.devices.mobile", 2);
   Service.sync();
 
   do_check_eq(syncFailures, 1);
   do_check_true(scheduler.numClients > 1);
   do_check_eq(scheduler.syncInterval, scheduler.activeInterval);
 
   Svc.Obs.remove("weave:service:sync:error", onSyncError);
   Service.startOver();
@@ -377,35 +378,36 @@ add_task(async function test_bug671378_s
 
       scheduler.scheduleNextSync();
       do_check_neq(scheduler.nextSync, 0);
       do_check_eq(scheduler.syncInterval, scheduler.singleDeviceInterval);
       do_check_eq(scheduler.syncTimer.delay, scheduler.singleDeviceInterval);
     });
   });
 
-  clientsEngine._store.create({id: "foo", cleartext: "bar"});
+  Service.clientsEngine._store.create({ id: "foo", cleartext: { name: "bar", type: "mobile" } });
   Service.sync();
   await promiseDone;
 });
 
 add_test(function test_adjust_timer_larger_syncInterval() {
   _("Test syncInterval > current timout period && nextSync != 0, syncInterval is NOT used.");
-  clientsEngine._store.create({id: "foo", cleartext: "bar"});
+  Svc.Prefs.set("clients.devices.mobile", 2);
   scheduler.updateClientMode();
   do_check_eq(scheduler.syncInterval, scheduler.activeInterval);
 
   scheduler.scheduleNextSync();
 
   // Ensure we have a small interval.
   do_check_neq(scheduler.nextSync, 0);
   do_check_eq(scheduler.syncTimer.delay, scheduler.activeInterval);
 
   // Make interval large again
   clientsEngine._wipeClient();
+  Svc.Prefs.reset("clients.devices.mobile");
   scheduler.updateClientMode();
   do_check_eq(scheduler.syncInterval, scheduler.singleDeviceInterval);
 
   scheduler.scheduleNextSync();
 
   // Ensure timer delay remains as the small interval.
   do_check_neq(scheduler.nextSync, 0);
   do_check_true(scheduler.syncTimer.delay <= scheduler.activeInterval);
@@ -419,17 +421,17 @@ add_test(function test_adjust_timer_smal
   _("Test current timout > syncInterval period && nextSync != 0, syncInterval is used.");
   scheduler.scheduleNextSync();
 
   // Ensure we have a large interval.
   do_check_neq(scheduler.nextSync, 0);
   do_check_eq(scheduler.syncTimer.delay, scheduler.singleDeviceInterval);
 
   // Make interval smaller
-  clientsEngine._store.create({id: "foo", cleartext: "bar"});
+  Svc.Prefs.set("clients.devices.mobile", 2);
   scheduler.updateClientMode();
   do_check_eq(scheduler.syncInterval, scheduler.activeInterval);
 
   scheduler.scheduleNextSync();
 
   // Ensure smaller timer delay is used.
   do_check_neq(scheduler.nextSync, 0);
   do_check_true(scheduler.syncTimer.delay <= scheduler.activeInterval);

--- a/services/sync/tests/unit/test_service_startOver.js
+++ b/services/sync/tests/unit/test_service_startOver.js
@@ -74,17 +74,17 @@ add_test(function test_removeClientData(
 
   run_next_test();
 });
 
 add_test(function test_reset_SyncScheduler() {
   // Some non-default values for SyncScheduler's attributes.
   Service.scheduler.idle = true;
   Service.scheduler.hasIncomingItems = true;
-  Service.scheduler.numClients = 42;
+  Svc.Prefs.set("clients.devices.desktop", 42);
   Service.scheduler.nextSync = Date.now();
   Service.scheduler.syncThreshold = MULTI_DEVICE_THRESHOLD;
   Service.scheduler.syncInterval = Service.scheduler.activeInterval;
 
   Service.startOver();
 
   do_check_false(Service.scheduler.idle);
   do_check_false(Service.scheduler.hasIncomingItems);

--- a/services/sync/tests/unit/test_syncscheduler.js
+++ b/services/sync/tests/unit/test_syncscheduler.js
@@ -162,29 +162,29 @@ add_test(function test_prefAttributes() 
 
 add_task(async function test_updateClientMode() {
   _("Test updateClientMode adjusts scheduling attributes based on # of clients appropriately");
   do_check_eq(scheduler.syncThreshold, SINGLE_USER_THRESHOLD);
   do_check_eq(scheduler.syncInterval, scheduler.singleDeviceInterval);
   do_check_false(scheduler.numClients > 1);
   do_check_false(scheduler.idle);
 
-  // Trigger a change in interval & threshold by adding a client.
-  clientsEngine._store.create(
-    { id: "foo", cleartext: { os: "mobile", version: "0.01", type: "desktop" } }
-  );
+  // Trigger a change in interval & threshold by noting there are multiple clients.
+  Svc.Prefs.set("clients.devices.desktop", 1);
+  Svc.Prefs.set("clients.devices.mobile", 1);
   scheduler.updateClientMode();
 
   do_check_eq(scheduler.syncThreshold, MULTI_DEVICE_THRESHOLD);
   do_check_eq(scheduler.syncInterval, scheduler.activeInterval);
   do_check_true(scheduler.numClients > 1);
   do_check_false(scheduler.idle);
 
   // Resets the number of clients to 0.
   clientsEngine.resetClient();
+  Svc.Prefs.reset("clients.devices.mobile");
   scheduler.updateClientMode();
 
   // Goes back to single user if # clients is 1.
   do_check_eq(scheduler.numClients, 1);
   do_check_eq(scheduler.syncThreshold, SINGLE_USER_THRESHOLD);
   do_check_eq(scheduler.syncInterval, scheduler.singleDeviceInterval);
   do_check_false(scheduler.numClients > 1);
   do_check_false(scheduler.idle);
@@ -597,34 +597,34 @@ add_task(async function test_idle_adjust
 
   // Single device: nothing changes.
   scheduler.observe(null, "idle", Svc.Prefs.get("scheduler.idleTime"));
   do_check_eq(scheduler.idle, true);
   do_check_eq(scheduler.syncInterval, scheduler.singleDeviceInterval);
 
   // Multiple devices: switch to idle interval.
   scheduler.idle = false;
-  clientsEngine._store.create(
-    { id: "foo", cleartext: { os: "mobile", version: "0.01", type: "desktop" } }
-  );
+  Svc.Prefs.set("clients.devices.desktop", 1);
+  Svc.Prefs.set("clients.devices.mobile", 1);
   scheduler.updateClientMode();
   scheduler.observe(null, "idle", Svc.Prefs.get("scheduler.idleTime"));
   do_check_eq(scheduler.idle, true);
   do_check_eq(scheduler.syncInterval, scheduler.idleInterval);
 
   await cleanUpAndGo();
 });
 
 add_task(async function test_back_triggersSync() {
   // Confirm defaults.
   do_check_false(scheduler.idle);
   do_check_eq(Status.backoffInterval, 0);
 
   // Set up: Define 2 clients and put the system in idle.
-  scheduler.numClients = 2;
+  Svc.Prefs.set("clients.devices.desktop", 1);
+  Svc.Prefs.set("clients.devices.mobile", 1);
   scheduler.observe(null, "idle", Svc.Prefs.get("scheduler.idleTime"));
   do_check_true(scheduler.idle);
 
   // We don't actually expect the sync (or the login, for that matter) to
   // succeed. We just want to ensure that it was attempted.
   let promiseObserved = promiseOneObserver("weave:service:login:error");
 
   // Send an 'active' event to trigger sync soonish.
@@ -635,17 +635,18 @@ add_task(async function test_back_trigge
 
 add_task(async function test_active_triggersSync_observesBackoff() {
   // Confirm defaults.
   do_check_false(scheduler.idle);
 
   // Set up: Set backoff, define 2 clients and put the system in idle.
   const BACKOFF = 7337;
   Status.backoffInterval = scheduler.idleInterval + BACKOFF;
-  scheduler.numClients = 2;
+  Svc.Prefs.set("clients.devices.desktop", 1);
+  Svc.Prefs.set("clients.devices.mobile", 1);
   scheduler.observe(null, "idle", Svc.Prefs.get("scheduler.idleTime"));
   do_check_eq(scheduler.idle, true);
 
   function onLoginStart() {
     do_throw("Shouldn't have kicked off a sync!");
   }
   Svc.Obs.add("weave:service:login:start", onLoginStart);
 
@@ -664,17 +665,18 @@ add_task(async function test_active_trig
 
 add_task(async function test_back_debouncing() {
   _("Ensure spurious back-then-idle events, as observed on OS X, don't trigger a sync.");
 
   // Confirm defaults.
   do_check_eq(scheduler.idle, false);
 
   // Set up: Define 2 clients and put the system in idle.
-  scheduler.numClients = 2;
+  Svc.Prefs.set("clients.devices.desktop", 1);
+  Svc.Prefs.set("clients.devices.mobile", 1);
   scheduler.observe(null, "idle", Svc.Prefs.get("scheduler.idleTime"));
   do_check_eq(scheduler.idle, true);
 
   function onLoginStart() {
     do_throw("Shouldn't have kicked off a sync!");
   }
   Svc.Obs.add("weave:service:login:start", onLoginStart);