--- a/browser/components/migration/AutoMigrate.jsm
+++ b/browser/components/migration/AutoMigrate.jsm
@@ -25,20 +25,21 @@ const kPasswordManagerTopicTypes = new S
 ]);
 
 const kSyncTopic = "fxaccounts:onlogin";
 
 const kNotificationId = "abouthome-automigration-undo";
 
 Cu.import("resource:///modules/MigrationUtils.jsm");
 Cu.import("resource://gre/modules/Preferences.jsm");
-Cu.import("resource://gre/modules/PlacesUtils.jsm");
 Cu.import("resource://gre/modules/Services.jsm");
 Cu.import("resource://gre/modules/Task.jsm");
 Cu.import("resource://gre/modules/XPCOMUtils.jsm");
+XPCOMUtils.defineLazyModuleGetter(this, "PlacesUtils",
+                                  "resource://gre/modules/PlacesUtils.jsm");
 
 const AutoMigrate = {
   get resourceTypesToUse() {
     let {BOOKMARKS, HISTORY, PASSWORDS} = Ci.nsIBrowserProfileMigrator;
     return BOOKMARKS | HISTORY | PASSWORDS;
   },
 
   _checkIfEnabled() {
@@ -385,14 +386,61 @@ const AutoMigrate = {
 
   UNDO_REMOVED_REASON_UNDO_USED: 0,
   UNDO_REMOVED_REASON_SYNC_SIGNIN: 1,
   UNDO_REMOVED_REASON_PASSWORD_CHANGE: 2,
   UNDO_REMOVED_REASON_BOOKMARK_CHANGE: 3,
   UNDO_REMOVED_REASON_OFFER_EXPIRED: 4,
   UNDO_REMOVED_REASON_OFFER_REJECTED: 5,
 
+  _removeUnchangedBookmarks: Task.async(function* (bookmarks) {
+    if (!bookmarks.length) {
+      return;
+    }
+
+    let guidToLMMap = new Map(bookmarks.map(b => [b.guid, b.lastModified]));
+    let bookmarksFromDB = [];
+    let bmPromises = Array.from(guidToLMMap.keys()).map(guid => {
+      // Ignore bookmarks where the promise doesn't resolve (ie that are missing)
+      // Also check that the bookmark fetch returns isn't null before adding it.
+      return PlacesUtils.bookmarks.fetch(guid).then(bm => bm && bookmarksFromDB.push(bm), () => {});
+    });
+    // We can't use the result of Promise.all because that would include nulls
+    // for bookmarks that no longer exist (which we're catching above).
+    yield Promise.all(bmPromises);
+    let unchangedBookmarks = bookmarksFromDB.filter(bm => {
+      return bm.lastModified.getTime() == guidToLMMap.get(bm.guid).getTime();
+    });
+
+    // We need to remove items with no ancestors first, followed by their
+    // parents, etc. In order to do this, find out how many ancestors each item
+    // has that also appear in our list of things to remove, and sort the items
+    // by those numbers. This ensures that children are always removed before
+    // their parents.
+    function determineAncestorCount(bm) {
+      if (bm._ancestorCount) {
+        return bm._ancestorCount;
+      }
+      let myCount = 0;
+      let parentBM = unchangedBookmarks.find(item => item.guid == bm.parentGuid);
+      if (parentBM) {
+        myCount = determineAncestorCount(parentBM) + 1;
+      }
+      bm._ancestorCount = myCount;
+      return myCount;
+    }
+    unchangedBookmarks.forEach(determineAncestorCount);
+    unchangedBookmarks.sort((a, b) => b._ancestorCount - a._ancestorCount);
+    for (let {guid} of unchangedBookmarks) {
+      yield PlacesUtils.bookmarks.remove(guid, {preventRemovalOfNonEmptyFolders: true}).catch(err => {
+        if (err && err.message != "Cannot remove a non-empty folder.") {
+          Cu.reportError(err);
+        }
+      });
+    }
+  }),
+
   QueryInterface: XPCOMUtils.generateQI(
     [Ci.nsIObserver, Ci.nsINavBookmarkObserver, Ci.nsISupportsWeakReference]
   ),
 };
 
 AutoMigrate.init();

--- a/browser/components/migration/MigrationUtils.jsm
+++ b/browser/components/migration/MigrationUtils.jsm
@@ -33,16 +33,19 @@ XPCOMUtils.defineLazyModuleGetter(this, 
 XPCOMUtils.defineLazyModuleGetter(this, "WindowsRegistry",
                                   "resource://gre/modules/WindowsRegistry.jsm");
 
 var gMigrators = null;
 var gProfileStartup = null;
 var gMigrationBundle = null;
 var gPreviousDefaultBrowserKey = "";
 
+let gKeepUndoData = false;
+let gUndoData = null;
+
 XPCOMUtils.defineLazyGetter(this, "gAvailableMigratorKeys", function() {
   if (AppConstants.platform == "win") {
     return [
       "firefox", "edge", "ie", "chrome", "chromium", "360se",
       "canary"
     ];
   }
   if (AppConstants.platform == "macosx") {
@@ -943,29 +946,79 @@ this.MigrationUtils = Object.freeze({
   _importQuantities: {
     bookmarks: 0,
     logins: 0,
     history: 0,
   },
 
   insertBookmarkWrapper(bookmark) {
     this._importQuantities.bookmarks++;
-    return PlacesUtils.bookmarks.insert(bookmark);
+    let insertionPromise = PlacesUtils.bookmarks.insert(bookmark);
+    if (!gKeepUndoData) {
+      return insertionPromise;
+    }
+    // If we keep undo data, add a promise handler that stores the undo data once
+    // the bookmark has been inserted in the DB, and then returns the bookmark.
+    let {parentGuid} = bookmark;
+    return insertionPromise.then(bm => {
+      let {guid, lastModified, type} = bm;
+      gUndoData.get("bookmarks").push({
+        parentGuid, guid, lastModified, type
+      });
+      return bm;
+    });
   },
 
   insertVisitsWrapper(places, options) {
     this._importQuantities.history += places.length;
     return PlacesUtils.asyncHistory.updatePlaces(places, options);
   },
 
   insertLoginWrapper(login) {
     this._importQuantities.logins++;
     return LoginHelper.maybeImportLogin(login);
   },
 
+  initializeUndoData() {
+    gKeepUndoData = true;
+    gUndoData = new Map([["bookmarks", []], ["visits", new Map()], ["logins", []]]);
+  },
+
+  _postProcessUndoData: Task.async(function*(state) {
+    if (!state) {
+      return state;
+    }
+    let bookmarkFolders = state.get("bookmarks").filter(b => b.type == PlacesUtils.bookmarks.TYPE_FOLDER);
+
+    let bookmarkFolderData = [];
+    let bmPromises = bookmarkFolders.map(({guid}) => {
+      // Ignore bookmarks where the promise doesn't resolve (ie that are missing)
+      // Also check that the bookmark fetch returns isn't null before adding it.
+      return PlacesUtils.bookmarks.fetch(guid).then(bm => bm && bookmarkFolderData.push(bm), () => {});
+    });
+
+    yield Promise.all(bmPromises);
+    let folderLMMap = new Map(bookmarkFolderData.map(b => [b.guid, b.lastModified]));
+    for (let bookmark of bookmarkFolders) {
+      let lastModified = folderLMMap.get(bookmark.guid);
+      // If the bookmark was deleted, the map will be returning null, so check:
+      if (lastModified) {
+        bookmark.lastModified = lastModified;
+      }
+    }
+    return state;
+  }),
+
+  stopAndRetrieveUndoData() {
+    let undoData = gUndoData;
+    gUndoData = null;
+    gKeepUndoData = false;
+    return this._postProcessUndoData(undoData);
+  },
+
   /**
    * Cleans up references to migrators and nsIProfileInstance instances.
    */
   finishMigration: function MU_finishMigration() {
     gMigrators = null;
     gProfileStartup = null;
     gMigrationBundle = null;
   },

--- a/browser/components/migration/tests/unit/test_automigration.js
+++ b/browser/components/migration/tests/unit/test_automigration.js
@@ -256,35 +256,131 @@ add_task(function* checkUndoRemoval() {
 add_task(function* checkUndoDisablingByBookmarksAndPasswords() {
   let startTime = "" + Date.now();
   Services.prefs.setCharPref("browser.migrate.automigrate.started", startTime);
   // Now set finished pref:
   let endTime = "" + (Date.now() + 1000);
   Services.prefs.setCharPref("browser.migrate.automigrate.finished", endTime);
   AutoMigrate.maybeInitUndoObserver();
 
-  ok(AutoMigrate.canUndo(), "Should be able to undo.");
+  Assert.ok(AutoMigrate.canUndo(), "Should be able to undo.");
 
   // Insert a login and check that that disabled undo.
   let login = Cc["@mozilla.org/login-manager/loginInfo;1"].createInstance(Ci.nsILoginInfo);
   login.init("www.mozilla.org", "http://www.mozilla.org", null, "user", "pass", "userEl", "passEl");
   Services.logins.addLogin(login);
 
-  ok(!AutoMigrate.canUndo(), "Should no longer be able to undo.");
+  Assert.ok(!AutoMigrate.canUndo(), "Should no longer be able to undo.");
   Services.prefs.setCharPref("browser.migrate.automigrate.started", startTime);
   Services.prefs.setCharPref("browser.migrate.automigrate.finished", endTime);
-  ok(AutoMigrate.canUndo(), "Should be able to undo.");
+  Assert.ok(AutoMigrate.canUndo(), "Should be able to undo.");
   AutoMigrate.maybeInitUndoObserver();
 
   // Insert a bookmark and check that that disabled undo.
   yield PlacesUtils.bookmarks.insert({
     parentGuid: PlacesUtils.bookmarks.toolbarGuid,
     url: "http://www.example.org/",
     title: "Some example bookmark",
   });
-  ok(!AutoMigrate.canUndo(), "Should no longer be able to undo.");
+  Assert.ok(!AutoMigrate.canUndo(), "Should no longer be able to undo.");
 
   try {
     Services.logins.removeAllLogins();
   } catch (ex) {}
   yield PlacesUtils.bookmarks.eraseEverything();
 });
 
+add_task(function* checkUndoBookmarksState() {
+  MigrationUtils.initializeUndoData();
+  const {TYPE_FOLDER, TYPE_BOOKMARK} = PlacesUtils.bookmarks;
+  let title = "Some example bookmark";
+  let url = "http://www.example.com";
+  let parentGuid = PlacesUtils.bookmarks.toolbarGuid;
+  let {guid, lastModified} = yield MigrationUtils.insertBookmarkWrapper({
+    title, url, parentGuid
+  });
+  Assert.deepEqual((yield MigrationUtils.stopAndRetrieveUndoData()).get("bookmarks"),
+      [{lastModified, parentGuid, guid, type: TYPE_BOOKMARK}]);
+
+  MigrationUtils.initializeUndoData();
+  ({guid, lastModified} = yield MigrationUtils.insertBookmarkWrapper({
+    title, parentGuid, type: TYPE_FOLDER
+  }));
+  let folder = {guid, lastModified, parentGuid, type: TYPE_FOLDER};
+  let folderGuid = folder.guid;
+  ({guid, lastModified} = yield MigrationUtils.insertBookmarkWrapper({
+    title, url, parentGuid: folderGuid
+  }));
+  let kid1 = {guid, lastModified, parentGuid: folderGuid, type: TYPE_BOOKMARK};
+  ({guid, lastModified} = yield MigrationUtils.insertBookmarkWrapper({
+    title, url, parentGuid: folderGuid
+  }));
+  let kid2 = {guid, lastModified, parentGuid: folderGuid, type: TYPE_BOOKMARK};
+
+  let bookmarksUndo = (yield MigrationUtils.stopAndRetrieveUndoData()).get("bookmarks");
+  Assert.equal(bookmarksUndo.length, 3);
+  // We expect that the last modified time from first kid #1 and then kid #2
+  // has been propagated to the folder:
+  folder.lastModified = kid2.lastModified;
+  // Not just using deepEqual on the entire array (which should work) because
+  // the failure messages get truncated by xpcshell which is unhelpful.
+  Assert.deepEqual(bookmarksUndo[0], folder);
+  Assert.deepEqual(bookmarksUndo[1], kid1);
+  Assert.deepEqual(bookmarksUndo[2], kid2);
+  yield PlacesUtils.bookmarks.eraseEverything();
+});
+
+add_task(function* testBookmarkRemovalByUndo() {
+  const {TYPE_FOLDER} = PlacesUtils.bookmarks;
+  MigrationUtils.initializeUndoData();
+  let title = "Some example bookmark";
+  let url = "http://www.mymagicaluniqueurl.com";
+  let parentGuid = PlacesUtils.bookmarks.toolbarGuid;
+  let {guid} = yield MigrationUtils.insertBookmarkWrapper({
+    title: "Some folder", parentGuid, type: TYPE_FOLDER
+  });
+  let folderGuid = guid;
+  let itemsToRemove = [];
+  ({guid} = yield MigrationUtils.insertBookmarkWrapper({
+    title: "Inner folder", parentGuid: folderGuid, type: TYPE_FOLDER
+  }));
+  let innerFolderGuid = guid;
+  itemsToRemove.push(innerFolderGuid);
+
+  ({guid} = yield MigrationUtils.insertBookmarkWrapper({
+    title: "Inner inner folder", parentGuid: innerFolderGuid, type: TYPE_FOLDER
+  }));
+  itemsToRemove.push(guid);
+
+  ({guid} = yield MigrationUtils.insertBookmarkWrapper({
+    title: "Inner nested item", url: "http://inner-nested-example.com", parentGuid: guid
+  }));
+  itemsToRemove.push(guid);
+
+  ({guid} = yield MigrationUtils.insertBookmarkWrapper({
+    title, url, parentGuid: folderGuid
+  }));
+  itemsToRemove.push(guid);
+
+  for (let toBeRemovedGuid of itemsToRemove) {
+    let dbResultForGuid = yield PlacesUtils.bookmarks.fetch(toBeRemovedGuid);
+    Assert.ok(dbResultForGuid, "Should be able to find items that will be removed.");
+  }
+  let bookmarkUndoState = (yield MigrationUtils.stopAndRetrieveUndoData()).get("bookmarks");
+  // Now insert a separate item into this folder, not related to the migration.
+  let newItem = yield PlacesUtils.bookmarks.insert(
+    {title: "Not imported", parentGuid: folderGuid, url: "http://www.example.com"}
+  );
+
+  yield AutoMigrate._removeUnchangedBookmarks(bookmarkUndoState);
+  Assert.ok(true, "Successfully removed imported items.");
+
+  let itemFromDB = yield PlacesUtils.bookmarks.fetch(newItem.guid);
+  Assert.ok(itemFromDB, "Item we inserted outside of migration is still there.");
+  itemFromDB = yield PlacesUtils.bookmarks.fetch(folderGuid);
+  Assert.ok(itemFromDB, "Folder we inserted in migration is still there because of new kids.");
+  for (let removedGuid of itemsToRemove) {
+    let dbResultForGuid = yield PlacesUtils.bookmarks.fetch(removedGuid);
+    let dbgStr = dbResultForGuid && dbResultForGuid.title;
+    Assert.equal(null, dbResultForGuid, "Should not be able to find items that should have been removed, but found " + dbgStr);
+  }
+  yield PlacesUtils.bookmarks.eraseEverything();
+});