--- a/mobile/android/services/src/main/java/org/mozilla/gecko/background/fxa/FxAccountClient.java
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/background/fxa/FxAccountClient.java
@@ -6,20 +6,18 @@ package org.mozilla.gecko.background.fxa
 
 import org.mozilla.gecko.background.fxa.FxAccountClient20.AccountStatusResponse;
 import org.mozilla.gecko.background.fxa.FxAccountClient20.RecoveryEmailStatusResponse;
 import org.mozilla.gecko.background.fxa.FxAccountClient20.RequestDelegate;
 import org.mozilla.gecko.background.fxa.FxAccountClient20.TwoKeys;
 import org.mozilla.gecko.fxa.devices.FxAccountDevice;
 import org.mozilla.gecko.sync.ExtendedJSONObject;
 
-import java.util.List;
-
 public interface FxAccountClient {
   public void accountStatus(String uid, RequestDelegate<AccountStatusResponse> requestDelegate);
   public void recoveryEmailStatus(byte[] sessionToken, RequestDelegate<RecoveryEmailStatusResponse> requestDelegate);
   public void keys(byte[] keyFetchToken, RequestDelegate<TwoKeys> requestDelegate);
   public void sign(byte[] sessionToken, ExtendedJSONObject publicKey, long certificateDurationInMilliseconds, RequestDelegate<String> requestDelegate);
   public void registerOrUpdateDevice(byte[] sessionToken, FxAccountDevice device, RequestDelegate<FxAccountDevice> requestDelegate);
   public void destroyDevice(byte[] sessionToken, String deviceId, RequestDelegate<ExtendedJSONObject> requestDelegate);
   public void deviceList(byte[] sessionToken, RequestDelegate<FxAccountDevice[]> requestDelegate);
-  public void notifyDevices(byte[] sessionToken, List<String> deviceIds, ExtendedJSONObject payload, Long TTL, RequestDelegate<ExtendedJSONObject> requestDelegate);
+  public void notifyDevices(byte[] sessionToken, ExtendedJSONObject body, RequestDelegate<ExtendedJSONObject> delegate);
 }

--- a/mobile/android/services/src/main/java/org/mozilla/gecko/background/fxa/FxAccountClient20.java
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/background/fxa/FxAccountClient20.java
@@ -30,17 +30,16 @@ import java.io.UnsupportedEncodingExcept
 import java.net.URI;
 import java.net.URISyntaxException;
 import java.net.URLEncoder;
 import java.security.GeneralSecurityException;
 import java.security.InvalidKeyException;
 import java.security.NoSuchAlgorithmException;
 import java.util.Arrays;
 import java.util.HashMap;
-import java.util.List;
 import java.util.Locale;
 import java.util.Map;
 import java.util.Map.Entry;
 import java.util.concurrent.Executor;
 
 import javax.crypto.Mac;
 
 import ch.boye.httpclientandroidlib.HttpEntity;
@@ -893,29 +892,28 @@ public class FxAccountClient20 implement
         }
       }
     };
 
     resource.get();
   }
 
   @Override
-  public void notifyDevices(@NonNull byte[] sessionToken, @NonNull List<String> deviceIds, ExtendedJSONObject payload, Long TTL, RequestDelegate<ExtendedJSONObject> delegate) {
+  public void notifyDevices(@NonNull byte[] sessionToken, ExtendedJSONObject body, RequestDelegate<ExtendedJSONObject> delegate) {
     final byte[] tokenId = new byte[32];
     final byte[] reqHMACKey = new byte[32];
     final byte[] requestKey = new byte[32];
     try {
       HKDF.deriveMany(sessionToken, new byte[0], FxAccountUtils.KW("sessionToken"), tokenId, reqHMACKey, requestKey);
     } catch (Exception e) {
       invokeHandleError(delegate, e);
       return;
     }
 
     final BaseResource resource;
-    final ExtendedJSONObject body = createNotifyDevicesBody(deviceIds, payload, TTL);
     try {
       resource = getBaseResource("account/devices/notify");
     } catch (URISyntaxException | UnsupportedEncodingException e) {
       invokeHandleError(delegate, e);
       return;
     }
 
     resource.delegate = new ResourceDelegate<ExtendedJSONObject>(resource, delegate, ResponseType.JSON_OBJECT, tokenId, reqHMACKey) {
@@ -926,25 +924,9 @@ public class FxAccountClient20 implement
         } catch (Exception e) {
           delegate.handleError(e);
         }
       }
     };
 
     post(resource, body);
   }
-
-  @NonNull
-  @SuppressWarnings("unchecked")
-  private ExtendedJSONObject createNotifyDevicesBody(@NonNull List<String> deviceIds, ExtendedJSONObject payload, Long TTL) {
-    final ExtendedJSONObject body = new ExtendedJSONObject();
-    final JSONArray to = new JSONArray();
-    to.addAll(deviceIds);
-    body.put("to", to);
-    if (payload != null) {
-      body.put("payload", payload);
-    }
-    if (TTL != null) {
-      body.put("TTL", TTL);
-    }
-    return body;
-  }
 }

--- a/mobile/android/services/src/main/java/org/mozilla/gecko/sync/stage/SyncClientsEngineStage.java
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/sync/stage/SyncClientsEngineStage.java
@@ -123,30 +123,35 @@ public class SyncClientsEngineStage exte
     @Override
     public String ifUnmodifiedSince() {
       // TODO last client download time?
       return null;
     }
 
     @Override
     public void handleRequestSuccess(SyncStorageResponse response) {
+      final Context context = session.getContext();
+      final Account account = FirefoxAccounts.getFirefoxAccount(context);
+      final AndroidFxAccount fxAccount = new AndroidFxAccount(context, account);
 
       // Hang onto the server's last modified timestamp to use
       // in X-If-Unmodified-Since for upload.
       session.config.persistServerClientsTimestamp(response.normalizedWeaveTimestamp());
       BaseResource.consumeEntity(response);
 
       // Wipe the clients table if it still hasn't been wiped but needs to be.
       wipeAndStore(null);
 
       // If we successfully downloaded all records but ours was not one of them
       // then reset the timestamp.
+      boolean isFirstLocalClientRecordUpload = false;
       if (!localAccountGUIDDownloaded) {
         Logger.info(LOG_TAG, "Local client GUID does not exist on the server. Upload timestamp will be reset.");
         session.config.persistServerClientRecordTimestamp(0);
+        isFirstLocalClientRecordUpload = true;
       }
       localAccountGUIDDownloaded = false;
 
       final int clientsCount;
       try {
         clientsCount = getClientsCount();
       } finally {
         // Close the database to clear cached readableDatabase/writableDatabase
@@ -171,67 +176,102 @@ public class SyncClientsEngineStage exte
             devicesToNotify.add(record.fxaDeviceId);
           }
         }
 
         // This method is synchronous, there's no risk of notifying the clients
         // before we actually uploaded the records
         uploadRemoteRecords();
 
-        // Notify the clients who got their record written
-        notifyClients(devicesToNotify);
+        // We will send a push notification later anyway.
+        if (!isFirstLocalClientRecordUpload) {
+          // Notify the clients who got their record written
+          notifyClients(fxAccount, devicesToNotify);
+        }
 
         return;
       }
       checkAndUpload();
+      if (isFirstLocalClientRecordUpload) {
+        notifyAllClients(fxAccount);
+      }
     }
 
-    private void notifyClients(final List<String> devicesToNotify) {
-      final ExecutorService executor = Executors.newSingleThreadExecutor();
-      final Context context = session.getContext();
-      final Account account = FirefoxAccounts.getFirefoxAccount(context);
-      if (account == null) {
-        Log.e(LOG_TAG, "Can't notify other clients: no account");
-        return;
-      }
-      final AndroidFxAccount fxAccount = new AndroidFxAccount(context, account);
-      final ExtendedJSONObject payload = createNotifyDevicesPayload();
+    private void notifyClients(@NonNull AndroidFxAccount fxAccount, @NonNull List<String> devicesToNotify) {
+      final ExtendedJSONObject body = createNotifyClientsBody(devicesToNotify);
+      notifyClientsHelper(fxAccount, body);
+    }
 
+    private void notifyAllClients(@NonNull AndroidFxAccount fxAccount) {
+      final ExtendedJSONObject body = createNotifyAllClientsBody(fxAccount.getDeviceId());
+      notifyClientsHelper(fxAccount, body);
+    }
+
+    private void notifyClientsHelper(@NonNull AndroidFxAccount fxAccount, @NonNull ExtendedJSONObject body) {
       final byte[] sessionToken;
       try {
         sessionToken = fxAccount.getState().getSessionToken();
       } catch (State.NotASessionTokenState e) {
         // Most of the time we should never reach this, but there can be races with the account
         // state, so better safe than sorry.
         Log.e(LOG_TAG, "Could not get a session token during Sync (?)", e);
         return;
       }
 
+      final ExecutorService executor = Executors.newSingleThreadExecutor();
       // API doc : https://github.com/mozilla/fxa-auth-server/blob/master/docs/api.md#post-v1accountdevicesnotify
       final FxAccountClient fxAccountClient = new FxAccountClient20(fxAccount.getAccountServerURI(), executor);
-      fxAccountClient.notifyDevices(sessionToken, devicesToNotify, payload, NOTIFY_TAB_SENT_TTL_SECS, new FxAccountClient20.RequestDelegate<ExtendedJSONObject>() {
+      fxAccountClient.notifyDevices(sessionToken, body, new FxAccountClient20.RequestDelegate<ExtendedJSONObject>() {
         @Override
         public void handleError(Exception e) {
           Log.e(LOG_TAG, "Error while notifying devices", e);
         }
 
         @Override
         public void handleFailure(FxAccountClientException.FxAccountClientRemoteException e) {
           Log.e(LOG_TAG, "Error while notifying devices", e);
         }
 
         @Override
         public void handleSuccess(ExtendedJSONObject result) {
-          Log.i(LOG_TAG, devicesToNotify.size() + " devices notified");
+          Log.i(LOG_TAG, "Devices notified");
         }
       });
     }
 
     @NonNull
     @SuppressWarnings("unchecked")
+    private ExtendedJSONObject createNotifyClientsBody(@NonNull List<String> devicesToNotify) {
+      final ExtendedJSONObject body = new ExtendedJSONObject();
+      final JSONArray to = new JSONArray();
+      to.addAll(devicesToNotify);
+      body.put("to", to);
+      createNotifyClientsHelper(body);
+      return body;
+    }
+
+    @NonNull
+    @SuppressWarnings("unchecked")
+    private ExtendedJSONObject createNotifyAllClientsBody(@NonNull String localFxADeviceId) {
+      final ExtendedJSONObject body = new ExtendedJSONObject();
+      body.put("to", "all");
+      final JSONArray excluded = new JSONArray();
+      excluded.add(localFxADeviceId);
+      body.put("excluded", excluded);
+      createNotifyClientsHelper(body);
+      return body;
+    }
+
+    private void createNotifyClientsHelper(ExtendedJSONObject body) {
+      body.put("payload", createNotifyDevicesPayload());
+      body.put("TTL", NOTIFY_TAB_SENT_TTL_SECS);
+    }
+
+    @NonNull
+    @SuppressWarnings("unchecked")
     private ExtendedJSONObject createNotifyDevicesPayload() {
       final ExtendedJSONObject payload = new ExtendedJSONObject();
       payload.put("version", 1);
       payload.put("command", "sync:collection_changed");
       final ExtendedJSONObject data = new ExtendedJSONObject();
       final JSONArray collections = new JSONArray();
       collections.add("clients");
       data.put("collections", collections);

--- a/mobile/android/tests/background/junit4/src/org/mozilla/gecko/fxa/login/MockFxAccountClient.java
+++ b/mobile/android/tests/background/junit4/src/org/mozilla/gecko/fxa/login/MockFxAccountClient.java
@@ -1,16 +1,17 @@
 /* Any copyright is dedicated to the Public Domain.
    http://creativecommons.org/publicdomain/zero/1.0/ */
 
 package org.mozilla.gecko.fxa.login;
 
 import android.text.TextUtils;
 
 import org.mozilla.gecko.background.fxa.FxAccountClient;
+import org.mozilla.gecko.background.fxa.FxAccountClient20;
 import org.mozilla.gecko.background.fxa.FxAccountClient20.AccountStatusResponse;
 import org.mozilla.gecko.background.fxa.FxAccountClient20.RequestDelegate;
 import org.mozilla.gecko.background.fxa.FxAccountClient20.RecoveryEmailStatusResponse;
 import org.mozilla.gecko.background.fxa.FxAccountClient20.TwoKeys;
 import org.mozilla.gecko.background.fxa.FxAccountClient20.LoginResponse;
 import org.mozilla.gecko.background.fxa.FxAccountClientException.FxAccountClientRemoteException;
 import org.mozilla.gecko.background.fxa.FxAccountRemoteError;
 import org.mozilla.gecko.background.fxa.FxAccountUtils;
@@ -234,12 +235,12 @@ public class MockFxAccountClient impleme
       return;
     }
     Collection<FxAccountDevice> devices = user.devices.values();
     FxAccountDevice[] devicesArray = devices.toArray(new FxAccountDevice[devices.size()]);
     requestDelegate.handleSuccess(devicesArray);
   }
 
   @Override
-  public void notifyDevices(byte[] sessionToken, List<String> deviceIds, ExtendedJSONObject payload, Long TTL, RequestDelegate<ExtendedJSONObject> requestDelegate) {
+  public void notifyDevices(byte[] sessionToken, ExtendedJSONObject body, RequestDelegate<ExtendedJSONObject> requestDelegate) {
     requestDelegate.handleSuccess(new ExtendedJSONObject());
   }
 }