--- a/services/fxaccounts/FxAccounts.jsm
+++ b/services/fxaccounts/FxAccounts.jsm
@@ -64,16 +64,17 @@ var publicProperties = [
   "requiresHttps",
   "resendVerificationEmail",
   "resetCredentials",
   "sessionStatus",
   "setProfileCache",
   "setSignedInUser",
   "signOut",
   "updateDeviceRegistration",
+  "deleteDeviceRegistration",
   "updateUserAccountData",
   "whenVerified",
 ];
 
 // An AccountState object holds all state related to one specific account.
 // Only one AccountState is ever "current" in the FxAccountsInternal object -
 // whenever a user logs out or logs in, the current AccountState is discarded,
 // making it impossible for the wrong state or state data to be accidentally
@@ -541,17 +542,23 @@ FxAccountsInternal.prototype = {
    *          verified: true/false
    *        }
    * @return Promise
    *         The promise resolves to null when the data is saved
    *         successfully and is rejected on error.
    */
   setSignedInUser: function setSignedInUser(credentials) {
     log.debug("setSignedInUser - aborting any existing flows");
-    return this.abortExistingFlow().then(() => {
+    return this.getSignedInUser().then(signedInUser => {
+      if (signedInUser) {
+        return this.deleteDeviceRegistration(signedInUser.sessionToken, signedInUser.deviceId);
+      }
+    }).then(() =>
+      this.abortExistingFlow()
+    ).then(() => {
       let currentAccountState = this.currentAccountState = this.newAccountState(
         Cu.cloneInto(credentials, {}) // Pass a clone of the credentials object.
       );
       // This promise waits for storage, but not for verification.
       // We're telling the caller that this is durable now (although is that
       // really something we should commit to? Why not let the write happen in
       // the background? Already does for updateAccountData ;)
       return currentAccountState.promiseInitialized.then(() => {
@@ -562,17 +569,17 @@ FxAccountsInternal.prototype = {
 
         return this.updateDeviceRegistration();
       }).then(() => {
         Services.telemetry.getHistogramById("FXA_CONFIGURED").add(1);
         this.notifyObservers(ONLOGIN_NOTIFICATION);
       }).then(() => {
         return currentAccountState.resolve();
       });
-    })
+    });
   },
 
   /**
    * Update account data for the currently signed in user.
    *
    * @param credentials
    *        The credentials object containing the fields to be updated.
    *        This object must contain |email| and |uid| fields and they must
@@ -818,18 +825,18 @@ FxAccountsInternal.prototype = {
     // For now we assume the service being logged out from is Sync, so
     // we must tell the server to either destroy the device or sign out
     // (if no device exists). We might need to revisit this when this
     // FxA code is used in a context that isn't Sync.
 
     const options = { service: "sync" };
 
     if (deviceId) {
-      log.debug("destroying device and session");
-      return this.fxAccountsClient.signOutAndDestroyDevice(sessionToken, deviceId, options);
+      log.debug("destroying device, session and unsubscribing from FxA push");
+      return this.deleteDeviceRegistration(sessionToken, deviceId);
     }
 
     log.debug("destroying session");
     return this.fxAccountsClient.signOut(sessionToken, options);
   },
 
   /**
    * Check the status of the current session using cached credentials.
@@ -1531,16 +1538,41 @@ FxAccountsInternal.prototype = {
   updateDeviceRegistration() {
     return this.getSignedInUser().then(signedInUser => {
       if (signedInUser) {
         return this._registerOrUpdateDevice(signedInUser);
       }
     }).catch(error => this._logErrorAndResetDeviceRegistrationVersion(error));
   },
 
+  // Delete the Push Subscription and the device registration on the auth server.
+  // Returns a promise that always resolves, never rejects.
+  async deleteDeviceRegistration(sessionToken, deviceId) {
+    try {
+      // Allow tests to skip device registration because it makes remote requests to the auth server.
+      if (Services.prefs.getBoolPref("identity.fxaccounts.skipDeviceRegistration")) {
+        return Promise.resolve();
+      }
+    } catch (ignore) {}
+
+    try {
+      await this.fxaPushService.unsubscribe();
+      if (sessionToken && deviceId) {
+        await this.fxAccountsClient.signOutAndDestroyDevice(sessionToken, deviceId);
+      }
+      this.currentAccountState.updateUserAccountData({
+        deviceId: null,
+        deviceRegistrationVersion: null
+      });
+    } catch (err) {
+      log.error("Could not delete the device registration", err);
+    }
+    return Promise.resolve();
+  },
+
   handleDeviceDisconnection(deviceId) {
     return this.currentAccountState.getUserAccountData()
       .then(data => data ? data.deviceId : null)
       .then(localDeviceId => {
         if (!localDeviceId) {
           // We've already been logged out (and that logout is probably what
           // caused us to get here via push!), so don't make noise here.
           log.info(`Push request to disconnect, but we've already disconnected`);

--- a/services/fxaccounts/tests/xpcshell/test_accounts.js
+++ b/services/fxaccounts/tests/xpcshell/test_accounts.js
@@ -65,16 +65,19 @@ MockStorageManager.prototype = {
     return Promise.resolve();
   },
 
   getAccountData() {
     return Promise.resolve(this.accountData);
   },
 
   updateAccountData(updatedFields) {
+    if (!this.accountData) {
+      return Promise.resolve();
+    }
     for (let [name, value] of Object.entries(updatedFields)) {
       if (value == null) {
         delete this.accountData[name];
       } else {
         this.accountData[name] = value;
       }
     }
     return Promise.resolve();
@@ -251,16 +254,40 @@ add_task(function* test_get_signed_in_us
   let localOnly = true;
   yield account.signOut(localOnly);
 
   // user should be undefined after sign out
   result = yield account.getSignedInUser();
   do_check_eq(result, null);
 });
 
+add_task(function* test_set_signed_in_user_deletes_previous_device() {
+  _("Check setSignedInUser tries to delete a previous registered device");
+  let account = MakeFxAccounts();
+  let deleteDeviceRegistrationCalled = false;
+  let credentials = {
+    email: "foo@example.com",
+    uid: "1234@lcip.org",
+    assertion: "foobar",
+    sessionToken: "dead",
+    kA: "beef",
+    kB: "cafe",
+    verified: true
+  };
+  yield account.setSignedInUser(credentials);
+
+  account.internal.deleteDeviceRegistration = () => {
+    deleteDeviceRegistrationCalled = true;
+    return Promise.resolve(true);
+  }
+
+  yield account.setSignedInUser(credentials);
+  do_check_true(deleteDeviceRegistrationCalled);
+});
+
 add_task(function* test_update_account_data() {
   _("Check updateUserAccountData does the right thing.");
   let account = MakeFxAccounts();
   let credentials = {
     email: "foo@example.com",
     uid: "1234@lcip.org",
     assertion: "foobar",
     sessionToken: "dead",
@@ -956,42 +983,40 @@ add_task(function* test_sign_out_with_de
   yield fxa.internal.setSignedInUser(credentials);
 
   const user = yield fxa.internal.getUserAccountData();
   do_check_true(user);
   Object.keys(credentials).forEach(key => do_check_eq(credentials[key], user[key]));
 
   const spy = {
     signOut: { count: 0 },
-    signOutAndDeviceDestroy: { count: 0, args: [] }
+    deleteDeviceRegistration: { count: 0, args: [] }
   };
   const client = fxa.internal.fxAccountsClient;
   client.signOut = function() {
     spy.signOut.count += 1;
     return Promise.resolve();
   };
-  client.signOutAndDestroyDevice = function() {
-    spy.signOutAndDeviceDestroy.count += 1;
-    spy.signOutAndDeviceDestroy.args.push(arguments);
+  fxa.internal.deleteDeviceRegistration = function() {
+    spy.deleteDeviceRegistration.count += 1;
+    spy.deleteDeviceRegistration.args.push(arguments);
     return Promise.resolve();
   };
 
   const promise = new Promise(resolve => {
     makeObserver(ONLOGOUT_NOTIFICATION, () => {
       log.debug("test_sign_out_with_device observed onlogout");
       // user should be undefined after sign out
       fxa.internal.getUserAccountData().then(user2 => {
         do_check_eq(user2, null);
         do_check_eq(spy.signOut.count, 0);
-        do_check_eq(spy.signOutAndDeviceDestroy.count, 1);
-        do_check_eq(spy.signOutAndDeviceDestroy.args[0].length, 3);
-        do_check_eq(spy.signOutAndDeviceDestroy.args[0][0], credentials.sessionToken);
-        do_check_eq(spy.signOutAndDeviceDestroy.args[0][1], credentials.deviceId);
-        do_check_true(spy.signOutAndDeviceDestroy.args[0][2]);
-        do_check_eq(spy.signOutAndDeviceDestroy.args[0][2].service, "sync");
+        do_check_eq(spy.deleteDeviceRegistration.count, 1);
+        do_check_eq(spy.deleteDeviceRegistration.args[0].length, 2);
+        do_check_eq(spy.deleteDeviceRegistration.args[0][0], credentials.sessionToken);
+        do_check_eq(spy.deleteDeviceRegistration.args[0][1], credentials.deviceId);
         resolve();
       });
     });
   });
 
   yield fxa.signOut();
 
   yield promise;
@@ -1003,57 +1028,56 @@ add_task(function* test_sign_out_without
   const credentials = getTestUser("alice");
   delete credentials.deviceId;
   yield fxa.internal.setSignedInUser(credentials);
 
   yield fxa.internal.getUserAccountData();
 
   const spy = {
     signOut: { count: 0, args: [] },
-    signOutAndDeviceDestroy: { count: 0 }
+    deleteDeviceRegistration: { count: 0 }
   };
   const client = fxa.internal.fxAccountsClient;
   client.signOut = function() {
     spy.signOut.count += 1;
     spy.signOut.args.push(arguments);
     return Promise.resolve();
   };
-  client.signOutAndDestroyDevice = function() {
-    spy.signOutAndDeviceDestroy.count += 1;
+  fxa.internal.deleteDeviceRegistration = function() {
+    spy.deleteDeviceRegistration.count += 1;
     return Promise.resolve();
   };
 
   const promise = new Promise(resolve => {
     makeObserver(ONLOGOUT_NOTIFICATION, () => {
       log.debug("test_sign_out_without_device observed onlogout");
       // user should be undefined after sign out
       fxa.internal.getUserAccountData().then(user2 => {
         do_check_eq(user2, null);
         do_check_eq(spy.signOut.count, 1);
         do_check_eq(spy.signOut.args[0].length, 2);
         do_check_eq(spy.signOut.args[0][0], credentials.sessionToken);
         do_check_true(spy.signOut.args[0][1]);
         do_check_eq(spy.signOut.args[0][1].service, "sync");
-        do_check_eq(spy.signOutAndDeviceDestroy.count, 0);
+        do_check_eq(spy.deleteDeviceRegistration.count, 0);
         resolve();
       });
     });
   });
 
   yield fxa.signOut();
 
   yield promise;
 });
 
 add_task(function* test_sign_out_with_remote_error() {
   let fxa = new MockFxAccounts();
-  let client = fxa.internal.fxAccountsClient;
   let remoteSignOutCalled = false;
   // Force remote sign out to trigger an error
-  client.signOutAndDestroyDevice = function() { remoteSignOutCalled = true; throw "Remote sign out error"; };
+  fxa.internal.deleteDeviceRegistration = function() { remoteSignOutCalled = true; throw "Remote sign out error"; };
   let promiseLogout = new Promise(resolve => {
     makeObserver(ONLOGOUT_NOTIFICATION, function() {
       log.debug("test_sign_out_with_remote_error observed onlogout");
       resolve();
     });
   });
 
   let jane = getTestUser("jane");

--- a/services/fxaccounts/tests/xpcshell/test_accounts_device_registration.js
+++ b/services/fxaccounts/tests/xpcshell/test_accounts_device_registration.js
@@ -112,16 +112,19 @@ function MockFxAccounts(device = {}) {
             getKey(type) {
               return ChromeUtils.base64URLDecode(
                 type === "auth" ? BOGUS_AUTHKEY : BOGUS_PUBLICKEY,
                 { padding: "ignore" });
             }
           });
         });
       },
+      unsubscribe() {
+        return Promise.resolve();
+      }
     },
     DEVICE_REGISTRATION_VERSION
   });
 }
 
 add_task(function* test_updateDeviceRegistration_with_new_device() {
   const deviceName = "foo";
   const deviceType = "bar";
@@ -286,16 +289,48 @@ add_task(function* test_updateDeviceRegi
 
   const state = fxa.internal.currentAccountState;
   const data = yield state.getUserAccountData();
 
   do_check_null(data.deviceId);
   do_check_eq(data.deviceRegistrationVersion, DEVICE_REGISTRATION_VERSION);
 });
 
+add_task(function* test_deleteDeviceRegistration() {
+  const credentials = getTestUser("pb");
+  const fxa = new MockFxAccounts({ name: "my device" });
+  yield fxa.internal.setSignedInUser(credentials);
+
+  const state = fxa.internal.currentAccountState;
+  let data = yield state.getUserAccountData();
+  do_check_eq(data.deviceId, credentials.deviceId);
+  do_check_eq(data.deviceRegistrationVersion, DEVICE_REGISTRATION_VERSION);
+
+  const spy = {
+    signOutAndDestroyDevice: { count: 0, args: [] }
+  };
+  const client = fxa.internal.fxAccountsClient;
+  client.signOutAndDestroyDevice = function() {
+    spy.signOutAndDestroyDevice.count += 1;
+    spy.signOutAndDestroyDevice.args.push(arguments);
+    return Promise.resolve({});
+  };
+  yield fxa.deleteDeviceRegistration(credentials.sessionToken, credentials.deviceId);
+
+  do_check_eq(spy.signOutAndDestroyDevice.count, 1);
+  do_check_eq(spy.signOutAndDestroyDevice.args[0].length, 2);
+  do_check_eq(spy.signOutAndDestroyDevice.args[0][0], credentials.sessionToken);
+  do_check_eq(spy.signOutAndDestroyDevice.args[0][1], credentials.deviceId);
+
+  data = yield state.getUserAccountData();
+
+  do_check_false(data.deviceId);
+  do_check_false(data.deviceRegistrationVersion);
+});
+
 add_task(function* test_updateDeviceRegistration_with_device_session_conflict_error() {
   const deviceName = "foo";
   const deviceType = "bar";
 
   const credentials = getTestUser("baz");
   const fxa = new MockFxAccounts({ name: deviceName });
   yield fxa.internal.setSignedInUser(credentials);
 

--- a/services/sync/tps/extensions/tps/resource/auth/fxaccounts.jsm
+++ b/services/sync/tps/extensions/tps/resource/auth/fxaccounts.jsm
@@ -106,16 +106,16 @@ var Authentication = {
       let user = Authentication.getSignedInUser();
       if (!user) {
         throw new Error("Failed to get signed in user!");
       }
       let fxc = new FxAccountsClient();
       let { sessionToken, deviceId } = user;
       if (deviceId) {
         Logger.logInfo("Destroying device " + deviceId);
-        Async.promiseSpinningly(fxc.signOutAndDestroyDevice(sessionToken, deviceId, { service: "sync" }));
+        Async.promiseSpinningly(fxAccounts.deleteDeviceRegistration(sessionToken, deviceId));
       } else {
         Logger.logError("No device found.");
         Async.promiseSpinningly(fxc.signOut(sessionToken, { service: "sync" }));
       }
     }
   }
 };