--- a/services/fxaccounts/FxAccounts.jsm
+++ b/services/fxaccounts/FxAccounts.jsm
@@ -413,31 +413,31 @@ FxAccountsInternal.prototype = {
     return new AccountState(storage);
   },
 
   /**
    * Send a message to a set of devices in the same account
    *
    * @return Promise
    */
-  notifyDevices(deviceIds, payload, TTL) {
-    if (!Array.isArray(deviceIds)) {
+  notifyDevices(deviceIds, excludedIds, payload, TTL) {
+    if (typeof deviceIds == "string") {
       deviceIds = [deviceIds];
     }
     return this.currentAccountState.getUserAccountData()
       .then(data => {
         if (!data) {
           throw this._error(ERROR_NO_ACCOUNT);
         }
         if (!data.sessionToken) {
           throw this._error(ERROR_AUTH_ERROR,
             "notifyDevices called without a session token");
         }
         return this.fxAccountsClient.notifyDevices(data.sessionToken, deviceIds,
-          payload, TTL);
+          excludedIds, payload, TTL);
     });
   },
 
   /**
    * Return the current time in milliseconds as an integer.  Allows tests to
    * manipulate the date to simulate certificate expiration.
    */
   now() {

--- a/services/fxaccounts/FxAccountsClient.jsm
+++ b/services/fxaccounts/FxAccountsClient.jsm
@@ -417,29 +417,37 @@ this.FxAccountsClient.prototype = {
   /**
    * Sends a message to other devices. Must conform with the push payload schema:
    * https://github.com/mozilla/fxa-auth-server/blob/master/docs/pushpayloads.schema.json
    *
    * @method notifyDevice
    * @param  sessionTokenHex
    *         Session token obtained from signIn
    * @param  deviceIds
-   *         Devices to send the message to
+   *         Devices to send the message to. If null, will be sent to all devices.
+   * @param  excludedIds
+   *         Devices to exclude when sending to all devices (deviceIds must be null).
    * @param  payload
    *         Data to send with the message
    * @return Promise
    *         Resolves to an empty object:
    *         {}
    */
-  notifyDevices(sessionTokenHex, deviceIds, payload, TTL = 0) {
+  notifyDevices(sessionTokenHex, deviceIds, excludedIds, payload, TTL = 0) {
+    if (deviceIds && excludedIds) {
+      throw new Error("You cannot specify excluded devices if deviceIds is set.")
+    }
     const body = {
-      to: deviceIds,
+      to: deviceIds || "all",
       payload,
       TTL
     };
+    if (excludedIds) {
+      body.excluded = excludedIds;
+    }
     return this._request("/account/devices/notify", "POST",
       deriveHawkCredentials(sessionTokenHex, "sessionToken"), body);
   },
 
   /**
    * Update the session or name for an existing device
    *
    * @method updateDevice

--- a/services/sync/modules/engines/clients.js
+++ b/services/sync/modules/engines/clients.js
@@ -308,16 +308,17 @@ ClientEngine.prototype = {
       this._log.error("Could not retrieve the FxA device list", ex);
       this._knownStaleFxADeviceIds = [];
       return;
     }
     this._knownStaleFxADeviceIds = Utils.arraySub(localClients, fxaClients);
   },
 
   _syncStartup() {
+    this.isFirstSync = !this.lastRecordUpload;
     // 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);
   },
 
@@ -391,16 +392,20 @@ ClientEngine.prototype = {
   },
 
   _onRecordsWritten(succeeded, failed) {
     // Reconcile the status of the local records with what we just wrote on the
     // server
     for (let id of succeeded) {
       const commandChanges = this._currentlySyncingCommands[id];
       if (id == this.localID) {
+        if (this.isFirstSync) {
+          this._log.info("Uploaded our client record for the first time, notifying other clients.");
+          this._notifyCollectionChanged();
+        }
         if (this.localCommands) {
           this.localCommands = this.localCommands.filter(command => !hasDupeCommand(commandChanges, command));
         }
       } else {
         const clientRecord = this._store._remoteClients[id];
         if (!commandChanges || !clientRecord) {
           // should be impossible, else we wouldn't have been writing it.
           this._log.warn("No command/No record changes for a client we uploaded");
@@ -428,29 +433,38 @@ ClientEngine.prototype = {
     const idsToNotify = succeeded.reduce((acc, id) => {
       if (id == this.localID) {
         return acc;
       }
       const fxaDeviceId = this.getClientFxaDeviceId(id);
       return fxaDeviceId ? acc.concat(fxaDeviceId) : acc;
     }, []);
     if (idsToNotify.length > 0) {
-      this._notifyCollectionChanged(idsToNotify);
+      this._notifyCollectionChanged(idsToNotify, NOTIFY_TAB_SENT_TTL_SECS);
     }
   },
 
-  _notifyCollectionChanged(ids) {
+  async _notifyCollectionChanged(ids = null, ttl = 0) {
     const message = {
       version: 1,
       command: "sync:collection_changed",
       data: {
         collections: ["clients"]
       }
     };
-    this.fxAccounts.notifyDevices(ids, message, NOTIFY_TAB_SENT_TTL_SECS);
+    let excludedIds = null;
+    if (!ids) {
+      const localFxADeviceId = await fxAccounts.getDeviceId();
+      excludedIds = [localFxADeviceId];
+    }
+    try {
+      await this.fxAccounts.notifyDevices(ids, excludedIds, message, ttl);
+    } catch (e) {
+      this._log.error("Could not notify of changes in the collection", e);
+    }
   },
 
   _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) {

--- a/services/sync/tests/unit/head_helpers.js
+++ b/services/sync/tests/unit/head_helpers.js
@@ -13,16 +13,36 @@
 Cu.import("resource://services-common/async.js");
 Cu.import("resource://testing-common/services/common/utils.js");
 Cu.import("resource://testing-common/PlacesTestUtils.jsm");
 Cu.import("resource://services-sync/util.js");
 Cu.import("resource://gre/modules/XPCOMUtils.jsm");
 Cu.import("resource://gre/modules/PlacesUtils.jsm");
 Cu.import("resource://gre/modules/ObjectUtils.jsm");
 
+// ================================================
+// Load mocking/stubbing library, sinon
+// docs: http://sinonjs.org/releases/v2.3.2/
+Cu.import("resource://gre/modules/Timer.jsm");
+const {Loader} = Cu.import("resource://gre/modules/commonjs/toolkit/loader.js", {});
+const loader = new Loader.Loader({
+  paths: {
+    "": "resource://testing-common/",
+  },
+  globals: {
+    setTimeout,
+    setInterval,
+    clearTimeout,
+    clearInterval,
+  },
+});
+const require = Loader.Require(loader, {id: ""});
+const sinon = require("sinon-2.3.2");
+// ================================================
+
 XPCOMUtils.defineLazyGetter(this, "SyncPingSchema", function() {
   let ns = {};
   Cu.import("resource://gre/modules/FileUtils.jsm", ns);
   let stream = Cc["@mozilla.org/network/file-input-stream;1"]
                .createInstance(Ci.nsIFileInputStream);
   let jsonReader = Cc["@mozilla.org/dom/json;1"]
                    .createInstance(Components.interfaces.nsIJSON);
   let schema;

--- a/services/sync/tests/unit/test_clients_engine.js
+++ b/services/sync/tests/unit/test_clients_engine.js
@@ -811,16 +811,17 @@ add_task(async function test_clients_not
     commands: [],
     version: "48",
     fxaDeviceId: remoteId2,
     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: remoteId }]); }
   };
 
   try {
     _("Syncing.");
     engine._sync();
 
@@ -1434,27 +1435,28 @@ add_task(async function test_command_syn
     protocols: ["1.5"]
   }), Date.now() / 1000));
 
   try {
     equal(collection.count(), 2, "2 remote records written");
     engine._sync();
     equal(collection.count(), 3, "3 remote records written (+1 for the synced local record)");
 
-    let notifiedIds;
     engine.sendCommand("wipeAll", []);
     engine._tracker.addChangedID(engine.localID);
-    engine.getClientFxaDeviceId = (id) => "fxa-" + id;
-    engine._notifyCollectionChanged = (ids) => (notifiedIds = ids);
+    const getClientFxaDeviceId = sinon.stub(engine, "getClientFxaDeviceId", (id) => "fxa-" + id);
+    const engineMock = sinon.mock(engine);
+    let _notifyCollectionChanged = engineMock.expects("_notifyCollectionChanged")
+                                             .withArgs(["fxa-" + remoteId, "fxa-" + remoteId2]);
     _("Syncing.");
     engine._sync();
-    deepEqual(notifiedIds, ["fxa-fake-guid-00", "fxa-fake-guid-01"]);
-    ok(!notifiedIds.includes(engine.getClientFxaDeviceId(engine.localID)),
-      "We never notify the local device");
+    _notifyCollectionChanged.verify();
 
+    engineMock.restore();
+    getClientFxaDeviceId.restore();
   } finally {
     cleanup();
     engine._tracker.clearChangedIDs();
 
     try {
       server.deleteCollections("foo");
     } finally {
       await promiseStopServer(server);
@@ -1533,13 +1535,49 @@ add_task(async function ensureSameFlowID
     equal(events[0].extra.reason, "testing");
     equal(events[1].extra.reason, "testing");
 
   } finally {
     Service.recordTelemetryEvent = origRecordTelemetryEvent;
   }
 });
 
+add_task(async function test_other_clients_notified_on_first_sync() {
+  _("Ensure that other clients are notified when we upload our client record for the first time.");
+
+  engine.resetLastSync();
+  engine._store.wipe();
+  generateNewKeys(Service.collectionKeys);
+
+  let server = serverForFoo(engine);
+  await SyncTestingInfrastructure(server);
+
+  const fxAccounts = engine.fxAccounts;
+  let calls = 0;
+  engine.fxAccounts = {
+    getDeviceId() { return fxAccounts.getDeviceId(); },
+    notifyDevices() {
+      calls++;
+      return Promise.resolve(true);
+    }
+  };
+
+  try {
+    engine.lastRecordUpload = 0;
+    _("First sync, should notify other clients");
+    engine._sync();
+    equal(calls, 1);
+
+    _("Second sync, should not notify other clients");
+    engine._sync();
+    equal(calls, 1);
+  } finally {
+    engine.fxAccounts = fxAccounts;
+    cleanup();
+    await promiseStopServer(server);
+  }
+});
+
 function run_test() {
   initTestLogging("Trace");
   Log.repository.getLogger("Sync.Engine.Clients").level = Log.Level.Trace;
   run_next_test();
 }

--- a/services/sync/tests/unit/test_uistate.js
+++ b/services/sync/tests/unit/test_uistate.js
@@ -1,33 +1,13 @@
 /* Any copyright is dedicated to the Public Domain.
    http://creativecommons.org/publicdomain/zero/1.0/ */
 
 "use strict";
 
-// ================================================
-// Load mocking/stubbing library, sinon
-// docs: http://sinonjs.org/releases/v2.3.2/
-Cu.import("resource://gre/modules/Timer.jsm");
-const {Loader} = Cu.import("resource://gre/modules/commonjs/toolkit/loader.js", {});
-const loader = new Loader.Loader({
-  paths: {
-    "": "resource://testing-common/",
-  },
-  globals: {
-    setTimeout,
-    setInterval,
-    clearTimeout,
-    clearInterval,
-  },
-});
-const require = Loader.Require(loader, {id: ""});
-const sinon = require("sinon-2.3.2");
-// ================================================
-
 Cu.import("resource://services-sync/UIState.jsm");
 
 const UIStateInternal = UIState._internal;
 
 add_task(async function test_isReady() {
   UIState.reset();
 
   let refreshState = sinon.spy(UIStateInternal, "refreshState");