--- a/services/sync/modules/engines.js
+++ b/services/sync/modules/engines.js
@@ -1786,16 +1786,21 @@ class Changeset {
     return this.changes[id];
   }
 
   // Adds a change for a tracked ID to the changeset.
   set(id, change) {
     this.changes[id] = change;
   }
 
+  // Adds multiple entries to the changeset.
+  insert(changes) {
+    Object.assign(this.changes, changes);
+  }
+
   // Indicates whether an entry is in the changeset.
   has(id) {
     return id in this.changes;
   }
 
   // Deletes an entry from the changeset. Used to clean up entries for
   // reconciled and successfully uploaded records.
   delete(id) {

--- a/services/sync/modules/engines/bookmarks.js
+++ b/services/sync/modules/engines/bookmarks.js
@@ -615,62 +615,19 @@ BookmarksEngine.prototype = {
   resetClient() {
     SyncEngine.prototype.resetClient.call(this);
     Async.promiseSpinningly(PlacesSyncUtils.bookmarks.reset());
   },
 
   // Called when _findDupe returns a dupe item and the engine has decided to
   // switch the existing item to the new incoming item.
   _switchItemToDupe(localDupeGUID, incomingItem) {
-    // We unconditionally change the item's ID in case the engine knows of
-    // an item but doesn't expose it through itemExists. If the API
-    // contract were stronger, this could be changed.
-    this._log.debug("Switching local ID to incoming: " + localDupeGUID + " -> " +
-                    incomingItem.id);
-    this._store.changeItemID(localDupeGUID, incomingItem.id);
-
-    // And mark the parent as being modified. Given we de-dupe based on the
-    // parent *name* it's possible the item having its GUID changed has a
-    // different parent from the incoming record.
-    // So we need to find the GUID of the local parent.
-    let now = this._tracker._now();
-    let localID = this._store.idForGUID(incomingItem.id);
-    let localParentID = PlacesUtils.bookmarks.getFolderIdForItem(localID);
-    let localParentGUID = this._store.GUIDForId(localParentID);
-    this._modified.set(localParentGUID, { modified: now, deleted: false });
-
-    // And we also add the parent as reflected in the incoming record as the
-    // de-dupe process might have used an existing item in a different folder.
-    // But only if the parent exists, otherwise we will upload a deleted item
-    // when it might actually be valid, just unknown to us. Note that this
-    // scenario will still leave us with inconsistent client and server states;
-    // the incoming record on the server references a parent that isn't the
-    // actual parent locally - see bug 1297955.
-    if (localParentGUID != incomingItem.parentid) {
-      let remoteParentID = this._store.idForGUID(incomingItem.parentid);
-      if (remoteParentID > 0) {
-        // The parent specified in the record does exist, so we are going to
-        // attempt a move when we come to applying the record. Mark the parent
-        // as being modified so we will later upload it with the new child
-        // reference.
-        this._modified.set(incomingItem.parentid, { modified: now, deleted: false });
-      } else {
-        // We aren't going to do a move as we don't have the parent (yet?).
-        // When applying the record we will add our special PARENT_ANNO
-        // annotation, so if it arrives in the future (either this Sync or a
-        // later one) it will be reparented.
-        this._log.debug(`Incoming duplicate item ${incomingItem.id} specifies ` +
-                        `non-existing parent ${incomingItem.parentid}`);
-      }
-    }
-
-    // The local, duplicate ID is always deleted on the server - but for
-    // bookmarks it is a logical delete.
-    // Simply adding this (now non-existing) ID to the tracker is enough.
-    this._modified.set(localDupeGUID, { modified: now, deleted: true });
+    let newChanges = Async.promiseSpinningly(PlacesSyncUtils.bookmarks.dedupe(
+      localDupeGUID, incomingItem.id, incomingItem.parentid));
+    this._modified.insert(newChanges);
   },
 
   // Cleans up the Places root, reading list items (ignored in bug 762118,
   // removed in bug 1155684), and pinned sites.
   _shouldDeleteRemotely(incomingItem) {
     return FORBIDDEN_INCOMING_IDS.includes(incomingItem.id) ||
            FORBIDDEN_INCOMING_PARENT_IDS.includes(incomingItem.parentid);
   },
@@ -913,22 +870,16 @@ BookmarksStore.prototype = {
         if (!this._foldersToDelete.has(childSyncId)) {
           needUpdate.add(childSyncId);
         }
       }
     }
     return [...needUpdate];
   }),
 
-  changeItemID: function BStore_changeItemID(oldID, newID) {
-    this._log.debug("Changing GUID " + oldID + " to " + newID);
-
-    Async.promiseSpinningly(PlacesSyncUtils.bookmarks.changeGuid(oldID, newID));
-  },
-
   // Create a record starting from the weave id (places guid)
   createRecord: function createRecord(id, collection) {
     let item = Async.promiseSpinningly(PlacesSyncUtils.bookmarks.fetch(id));
     if (!item) { // deleted item
       let record = new PlacesItem(collection, id);
       record.deleted = true;
       return record;
     }

--- a/services/sync/tests/unit/test_bookmark_duping.js
+++ b/services/sync/tests/unit/test_bookmark_duping.js
@@ -288,17 +288,21 @@ add_task(function* test_dupe_reparented_
     };
 
     collection.insert(newGUID, encryptPayload(to_apply), Date.now() / 1000 + 10);
 
     // Make a change to the bookmark that's a dupe, and set the modification
     // time further in the future than the incoming record. This will cause
     // us to issue the infamous "DATA LOSS" warning in the logs but cause us
     // to *not* apply the incoming record.
-    engine._tracker.addChangedID(bmk1_guid, Date.now() / 1000 + 60);
+    yield PlacesTestUtils.setBookmarkSyncFields({
+      guid: bmk1_guid,
+      syncChangeCounter: 1,
+      lastModified: Date.now() + 60000,
+    });
 
     _("Syncing so new dupe record is processed");
     engine.lastSync = engine.lastSync - 0.01;
     engine.sync();
 
     // We should have logically deleted the dupe record.
     equal(collection.count(), 8);
     ok(getServerRecord(collection, bmk1_guid).deleted);

--- a/toolkit/components/places/PlacesSyncUtils.jsm
+++ b/toolkit/components/places/PlacesSyncUtils.jsm
@@ -285,38 +285,45 @@ const BookmarkSyncUtils = PlacesSyncUtil
           // Drop stale tombstones.
           yield db.executeCached("DELETE FROM moz_bookmarks_deleted");
         });
       }
     );
   }),
 
   /**
-   * Changes the GUID of an existing item. This method only allows Places GUIDs
-   * because root sync IDs cannot be changed.
+   * De-dupes an item by changing its sync ID to match the ID on the server.
+   * Sync calls this method when it detects an incoming item is a duplicate of
+   * an existing local item.
+   *
+   * Note that this method doesn't move the item if the local and remote sync
+   * IDs are different. That happens after de-duping, when the bookmarks engine
+   * calls `update` to update the item.
    *
-   * @return {Promise} resolved once the GUID has been changed.
-   * @resolves to the new GUID.
-   * @rejects if the old GUID does not exist.
+   * @param localSyncId
+   *        The local ID to change.
+   * @param remoteSyncId
+   *        The remote ID that should replace the local ID.
+   * @param remoteParentSyncId
+   *        The remote record's parent ID.
+   * @return {Promise} resolved once the ID has been changed.
+   * @resolves to an object containing new change records for the old item,
+   *           the local parent, and the remote parent if different from the
+   *           local parent. The bookmarks engine merges these records into the
+   *           changeset for the current sync.
    */
-  changeGuid: Task.async(function* (oldGuid, newGuid) {
-    PlacesUtils.BOOKMARK_VALIDATORS.guid(oldGuid);
-    PlacesUtils.BOOKMARK_VALIDATORS.guid(newGuid);
+  dedupe: Task.async(function* (localSyncId, remoteSyncId, remoteParentSyncId) {
+    PlacesUtils.SYNC_BOOKMARK_VALIDATORS.syncId(localSyncId);
+    PlacesUtils.SYNC_BOOKMARK_VALIDATORS.syncId(remoteSyncId);
+    PlacesUtils.SYNC_BOOKMARK_VALIDATORS.syncId(remoteParentSyncId);
 
-    let itemId = yield PlacesUtils.promiseItemId(oldGuid);
-    if (PlacesUtils.isRootItem(itemId)) {
-      throw new Error(`Cannot change GUID of Places root ${oldGuid}`);
-    }
-    return PlacesUtils.withConnectionWrapper("BookmarkSyncUtils: changeGuid",
-      Task.async(function* (db) {
-        yield db.executeCached(`UPDATE moz_bookmarks SET guid = :newGuid
-          WHERE id = :itemId`, { newGuid, itemId });
-        PlacesUtils.invalidateCachedGuidFor(itemId);
-        return newGuid;
-      })
+    return PlacesUtils.withConnectionWrapper("BookmarkSyncUtils: dedupe", db =>
+      dedupeSyncBookmark(db, BookmarkSyncUtils.syncIdToGuid(localSyncId),
+                         BookmarkSyncUtils.syncIdToGuid(remoteSyncId),
+                         BookmarkSyncUtils.syncIdToGuid(remoteParentSyncId))
     );
   }),
 
   /**
    * Updates a bookmark with synced properties. Only Sync should call this
    * method; other callers should use `Bookmarks.update`.
    *
    * The following properties are supported:
@@ -1380,16 +1387,103 @@ var pullSyncChanges = Task.async(functio
     { deletedSyncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL },
     row => addRowToChangeRecords(row, changeRecords));
 
   yield markChangesAsSyncing(db, changeRecords);
 
   return changeRecords;
 });
 
+var dedupeSyncBookmark = Task.async(function* (db, localGuid, remoteGuid,
+                                               remoteParentGuid) {
+  let rows = yield db.executeCached(`
+    SELECT b.id, p.guid AS parentGuid, b.syncStatus
+    FROM moz_bookmarks b
+    JOIN moz_bookmarks p ON p.id = b.parent
+    WHERE b.guid = :localGuid`,
+    { localGuid });
+  if (!rows.length) {
+    throw new Error(`Local item ${localGuid} does not exist`);
+  }
+
+  let localId = rows[0].getResultByName("id");
+  if (PlacesUtils.isRootItem(localId)) {
+    throw new Error(`Cannot de-dupe local root ${localGuid}`);
+  }
+
+  let localParentGuid = rows[0].getResultByName("parentGuid");
+  let sameParent = localParentGuid == remoteParentGuid;
+  let modified = PlacesUtils.toPRTime(Date.now());
+
+  yield db.executeTransaction(function* () {
+    // Change the item's old GUID to the new remote GUID. This will throw a
+    // constraint error if the remote GUID already exists locally.
+    BookmarkSyncLog.debug("dedupeSyncBookmark: Switching local GUID " +
+                          localGuid + " to incoming GUID " + remoteGuid);
+    yield db.executeCached(`UPDATE moz_bookmarks
+      SET guid = :remoteGuid
+      WHERE id = :localId`,
+      { remoteGuid, localId });
+    PlacesUtils.invalidateCachedGuidFor(localId);
+
+    // And mark the parent as being modified. Given we de-dupe based on the
+    // parent *name* it's possible the item having its GUID changed has a
+    // different parent from the incoming record.
+    // So we need to return a change record for the parent, and bump its
+    // counter to ensure we don't lose the change if the current sync is
+    // interrupted.
+    yield db.executeCached(`UPDATE moz_bookmarks
+      SET syncChangeCounter = syncChangeCounter + 1
+      WHERE guid = :localParentGuid`,
+      { localParentGuid });
+
+    // And we also add the parent as reflected in the incoming record as the
+    // de-dupe process might have used an existing item in a different folder.
+    // This statement is a no-op if we don't have the new parent yet, but that's
+    // fine: applying the record will add our special SYNC_PARENT_ANNO
+    // annotation and move it to unfiled. If the parent arrives in the future
+    // (either this Sync or a later one), the item will be reparented. Note that
+    // this scenario will still leave us with inconsistent client and server
+    // states; the incoming record on the server references a parent that isn't
+    // the actual parent locally - see bug 1297955.
+    if (!sameParent) {
+      yield db.executeCached(`UPDATE moz_bookmarks
+        SET syncChangeCounter = syncChangeCounter + 1
+        WHERE guid = :remoteParentGuid`,
+        { remoteParentGuid });
+    }
+
+    // The local, duplicate ID is always deleted on the server - but for
+    // bookmarks it is a logical delete.
+    let localSyncStatus = rows[0].getResultByName("syncStatus");
+    if (localSyncStatus == PlacesUtils.bookmarks.SYNC_STATUS.NORMAL) {
+      yield db.executeCached(`
+        INSERT INTO moz_bookmarks_deleted (guid, dateRemoved)
+        VALUES (:localGuid, :modified)`,
+        { localGuid, modified });
+    }
+  });
+
+  // TODO (Bug 1313890): Refactor the bookmarks engine to pull change records
+  // before uploading, instead of returning records to merge into the engine's
+  // initial changeset.
+  let changeRecords = yield pullSyncChanges(db);
+
+  if (BookmarkSyncLog.level <= Log.Level.Debug && !sameParent) {
+    let remoteParentSyncId = BookmarkSyncUtils.guidToSyncId(remoteParentGuid);
+    if (!changeRecords.hasOwnProperty(remoteParentSyncId)) {
+      BookmarkSyncLog.debug("dedupeSyncBookmark: Incoming duplicate item " +
+                            remoteGuid + " specifies non-existing parent " +
+                            remoteParentGuid);
+    }
+  }
+
+  return changeRecords;
+});
+
 /**
  * Updates the sync status on all "NEW" and "UNKNOWN" bookmarks to "NORMAL".
  *
  * We do this when pulling changes instead of in `pushChanges` to make sure
  * we write tombstones if a new item is deleted after an interrupted sync. (For
  * example, if a "NEW" record is uploaded or reconciled, then the app is closed
  * before Sync calls `pushChanges`).
  */

--- a/toolkit/components/places/tests/unit/test_sync_utils.js
+++ b/toolkit/components/places/tests/unit/test_sync_utils.js
@@ -220,44 +220,136 @@ add_task(function* test_order() {
     deepEqual(childSyncIds, [guids.childBmk, guids.siblingBmk, guids.siblingSep,
       guids.siblingFolder], "Nonexistent children should be ignored");
   }
 
   yield PlacesUtils.bookmarks.eraseEverything();
   yield PlacesSyncUtils.bookmarks.reset();
 });
 
-add_task(function* test_changeGuid_invalid() {
-  yield rejects(PlacesSyncUtils.bookmarks.changeGuid(makeGuid()),
-    "Should require a new GUID");
-  yield rejects(PlacesSyncUtils.bookmarks.changeGuid(makeGuid(), "!@#$"),
-    "Should reject invalid GUIDs");
-  yield rejects(PlacesSyncUtils.bookmarks.changeGuid(makeGuid(), makeGuid()),
-    "Should reject nonexistent item GUIDs");
-  yield rejects(
-    PlacesSyncUtils.bookmarks.changeGuid(PlacesUtils.bookmarks.menuGuid,
-      makeGuid()),
-    "Should reject roots");
-});
+add_task(function* test_dedupe() {
+  yield ignoreChangedRoots();
 
-add_task(function* test_changeGuid() {
-  let item = yield PlacesUtils.bookmarks.insert({
-    parentGuid: PlacesUtils.bookmarks.menuGuid,
-    type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+  let parentFolder = yield PlacesSyncUtils.bookmarks.insert({
+    kind: "folder",
+    syncId: makeGuid(),
+    parentSyncId: "menu",
+  });
+  let differentParentFolder = yield PlacesSyncUtils.bookmarks.insert({
+    kind: "folder",
+    syncId: makeGuid(),
+    parentSyncId: "menu",
+  });
+  let mozBmk = yield PlacesSyncUtils.bookmarks.insert({
+    kind: "bookmark",
+    syncId: makeGuid(),
+    parentSyncId: parentFolder.syncId,
     url: "https://mozilla.org",
   });
-  let id = yield PlacesUtils.promiseItemId(item.guid);
+  let fxBmk = yield PlacesSyncUtils.bookmarks.insert({
+    kind: "bookmark",
+    syncId: makeGuid(),
+    parentSyncId: parentFolder.syncId,
+    url: "http://getfirefox.com",
+  });
+  let tbBmk = yield PlacesSyncUtils.bookmarks.insert({
+    kind: "bookmark",
+    syncId: makeGuid(),
+    parentSyncId: parentFolder.syncId,
+    url: "http://getthunderbird.com",
+  });
+
+  yield rejects(
+    PlacesSyncUtils.bookmarks.dedupe(makeGuid(), makeGuid(), makeGuid()),
+    "Should reject attempts to de-dupe nonexistent items"
+  );
+  yield rejects(PlacesSyncUtils.bookmarks.dedupe("menu", makeGuid(), "places"),
+    "Should reject attempts to de-dupe local roots");
+
+  do_print("De-dupe with same remote parent");
+  {
+    let localId = yield PlacesUtils.promiseItemId(mozBmk.syncId);
+    let newRemoteSyncId = makeGuid();
+
+    let changes = yield PlacesSyncUtils.bookmarks.dedupe(
+      mozBmk.syncId, newRemoteSyncId, parentFolder.syncId);
+    deepEqual(Object.keys(changes).sort(), [
+      parentFolder.syncId, // Parent.
+      mozBmk.syncId, // Tombstone for old sync ID.
+    ].sort(), "Should bump change counter of parent");
+    ok(changes[mozBmk.syncId].tombstone,
+      "Should write tombstone for old local sync ID");
+    ok(Object.values(changes).every(change => change.counter === 1),
+      "Change counter for every bookmark should be 1");
+
+    ok(!(yield PlacesUtils.bookmarks.fetch(mozBmk.syncId)),
+      "Bookmark with old local sync ID should not exist");
+    yield rejects(PlacesUtils.promiseItemId(mozBmk.syncId),
+      "Should invalidate GUID cache entry for old local sync ID");
+
+    let newMozBmk = yield PlacesUtils.bookmarks.fetch(newRemoteSyncId);
+    equal(newMozBmk.guid, newRemoteSyncId,
+      "Should change local sync ID to remote sync ID");
+    equal(yield PlacesUtils.promiseItemId(newRemoteSyncId), localId,
+      "Should add new remote sync ID to GUID cache");
+
+    yield setChangesSynced(changes);
+  }
 
-  let newGuid = makeGuid();
-  let result = yield PlacesSyncUtils.bookmarks.changeGuid(item.guid, newGuid);
-  equal(result, newGuid, "Should return new GUID");
+  do_print("De-dupe with different remote parent");
+  {
+    let localId = yield PlacesUtils.promiseItemId(fxBmk.syncId);
+    let newRemoteSyncId = makeGuid();
+
+    let changes = yield PlacesSyncUtils.bookmarks.dedupe(
+      fxBmk.syncId, newRemoteSyncId, differentParentFolder.syncId);
+    deepEqual(Object.keys(changes).sort(), [
+      parentFolder.syncId, // Old local parent.
+      differentParentFolder.syncId, // New remote parent.
+      fxBmk.syncId, // Tombstone for old sync ID.
+    ].sort(), "Should bump change counter of old parent and new parent");
+    ok(changes[fxBmk.syncId].tombstone,
+      "Should write tombstone for old local sync ID");
+    ok(Object.values(changes).every(change => change.counter === 1),
+      "Change counter for every bookmark should be 1");
+
+    let newFxBmk = yield PlacesUtils.bookmarks.fetch(newRemoteSyncId);
+    equal(newFxBmk.parentGuid, parentFolder.syncId,
+      "De-duping should not move bookmark to new parent");
+    equal(yield PlacesUtils.promiseItemId(newRemoteSyncId), localId,
+      "De-duping with different remote parent should cache new sync ID");
+
+    yield setChangesSynced(changes);
+  }
 
-  equal(yield PlacesUtils.promiseItemId(newGuid), id, "Should map ID to new GUID");
-  yield rejects(PlacesUtils.promiseItemId(item.guid), "Should not map ID to old GUID");
-  equal(yield PlacesUtils.promiseItemGuid(id), newGuid, "Should map new GUID to ID");
+  do_print("De-dupe with nonexistent remote parent");
+  {
+    let localId = yield PlacesUtils.promiseItemId(tbBmk.syncId);
+    let newRemoteSyncId = makeGuid();
+    let remoteParentSyncId = makeGuid();
+
+    let changes = yield PlacesSyncUtils.bookmarks.dedupe(
+      tbBmk.syncId, newRemoteSyncId, remoteParentSyncId);
+    deepEqual(Object.keys(changes).sort(), [
+      parentFolder.syncId, // Old local parent.
+      tbBmk.syncId, // Tombstone for old sync ID.
+    ].sort(), "Should bump change counter of old parent");
+    ok(changes[tbBmk.syncId].tombstone,
+      "Should write tombstone for old local sync ID");
+    ok(Object.values(changes).every(change => change.counter === 1),
+      "Change counter for every bookmark should be 1");
+
+    equal(yield PlacesUtils.promiseItemId(newRemoteSyncId), localId,
+      "De-duping with nonexistent remote parent should cache new sync ID");
+
+    yield setChangesSynced(changes);
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 add_task(function* test_order_roots() {
   let oldOrder = yield PlacesSyncUtils.bookmarks.fetchChildSyncIds(
     PlacesUtils.bookmarks.rootGuid);
   yield PlacesSyncUtils.bookmarks.order(PlacesUtils.bookmarks.rootGuid,
     shuffle(oldOrder));
   let newOrder = yield PlacesSyncUtils.bookmarks.fetchChildSyncIds(