--- a/browser/components/migration/AutoMigrate.jsm
+++ b/browser/components/migration/AutoMigrate.jsm
@@ -33,16 +33,18 @@ Cu.import("resource://gre/modules/Prefer
 Cu.import("resource://gre/modules/Services.jsm");
 Cu.import("resource://gre/modules/Task.jsm");
 Cu.import("resource://gre/modules/XPCOMUtils.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "LoginHelper",
                                   "resource://gre/modules/LoginHelper.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "PlacesUtils",
                                   "resource://gre/modules/PlacesUtils.jsm");
 
+Cu.importGlobalProperties(["URL"]);
+
 const AutoMigrate = {
   get resourceTypesToUse() {
     let {BOOKMARKS, HISTORY, PASSWORDS} = Ci.nsIBrowserProfileMigrator;
     return BOOKMARKS | HISTORY | PASSWORDS;
   },
 
   _checkIfEnabled() {
     let pref = Preferences.get(kAutoMigrateEnabledPref, false);
@@ -448,14 +450,31 @@ const AutoMigrate = {
         foundLogin.QueryInterface(Ci.nsILoginMetaInfo);
         if (foundLogin.timePasswordChanged == login.timePasswordChanged) {
           Services.logins.removeLogin(foundLogin);
         }
       }
     }
   }),
 
+  _removeSomeVisits: Task.async(function* (visits) {
+    for (let urlVisits of visits) {
+      let urlObj;
+      try {
+        urlObj = new URL(urlVisits.url);
+      } catch (ex) {
+        continue;
+      }
+      yield PlacesUtils.history.removeVisitsByFilter({
+        url: urlObj,
+        beginDate: PlacesUtils.toDate(urlVisits.first),
+        endDate: PlacesUtils.toDate(urlVisits.last),
+        limit: urlVisits.visitCount,
+      });
+    }
+  }),
+
   QueryInterface: XPCOMUtils.generateQI(
     [Ci.nsIObserver, Ci.nsINavBookmarkObserver, Ci.nsISupportsWeakReference]
   ),
 };
 
 AutoMigrate.init();

--- a/browser/components/migration/MigrationUtils.jsm
+++ b/browser/components/migration/MigrationUtils.jsm
@@ -11,16 +11,18 @@ const TOPIC_WILL_IMPORT_BOOKMARKS = "ini
 const TOPIC_DID_IMPORT_BOOKMARKS = "initial-migration-did-import-default-bookmarks";
 const TOPIC_PLACES_DEFAULTS_FINISHED = "places-browser-init-complete";
 
 Cu.import("resource://gre/modules/AppConstants.jsm");
 Cu.import("resource://gre/modules/Services.jsm");
 Cu.import("resource://gre/modules/Task.jsm");
 Cu.import("resource://gre/modules/XPCOMUtils.jsm");
 
+Cu.importGlobalProperties(["URL"]);
+
 XPCOMUtils.defineLazyModuleGetter(this, "AutoMigrate",
                                   "resource:///modules/AutoMigrate.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "BookmarkHTMLUtils",
                                   "resource://gre/modules/BookmarkHTMLUtils.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "LoginHelper",
                                   "resource://gre/modules/LoginHelper.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "PlacesUtils",
                                   "resource://gre/modules/PlacesUtils.jsm");
@@ -964,16 +966,19 @@ this.MigrationUtils = Object.freeze({
         parentGuid, guid, lastModified, type
       });
       return bm;
     });
   },
 
   insertVisitsWrapper(places, options) {
     this._importQuantities.history += places.length;
+    if (gKeepUndoData) {
+      this._updateHistoryUndo(places);
+    }
     return PlacesUtils.asyncHistory.updatePlaces(places, options);
   },
 
   insertLoginWrapper(login) {
     this._importQuantities.logins++;
     let insertedLogin = LoginHelper.maybeImportLogin(login);
     // Note that this means that if we import a login that has a newer password
     // than we know about, we will update the login, and an undo of the import
@@ -982,17 +987,17 @@ this.MigrationUtils = Object.freeze({
     if (insertedLogin && gKeepUndoData) {
       let {guid, timePasswordChanged} = insertedLogin;
       gUndoData.get("logins").push({guid, timePasswordChanged});
     }
   },
 
   initializeUndoData() {
     gKeepUndoData = true;
-    gUndoData = new Map([["bookmarks", []], ["visits", new Map()], ["logins", []]]);
+    gUndoData = new Map([["bookmarks", []], ["visits", []], ["logins", []]]);
   },
 
   _postProcessUndoData: Task.async(function*(state) {
     if (!state) {
       return state;
     }
     let bookmarkFolders = state.get("bookmarks").filter(b => b.type == PlacesUtils.bookmarks.TYPE_FOLDER);
 
@@ -1017,16 +1022,42 @@ this.MigrationUtils = Object.freeze({
 
   stopAndRetrieveUndoData() {
     let undoData = gUndoData;
     gUndoData = null;
     gKeepUndoData = false;
     return this._postProcessUndoData(undoData);
   },
 
+  _updateHistoryUndo(places) {
+    let visits = gUndoData.get("visits");
+    let visitMap = new Map(visits.map(v => [v.url, v]));
+    for (let place of places) {
+      let visitCount = place.visits.length;
+      let first = Math.min.apply(Math, place.visits.map(v => v.visitDate));
+      let last = Math.max.apply(Math, place.visits.map(v => v.visitDate));
+      let url = place.uri.spec;
+      try {
+        new URL(url);
+      } catch (ex) {
+        // This won't save and we won't need to 'undo' it, so ignore this URL.
+        continue;
+      }
+      if (!visitMap.has(url)) {
+        visitMap.set(url, {url, visitCount, first, last});
+      } else {
+        let currentData = visitMap.get(url);
+        currentData.visitCount += visitCount;
+        currentData.first = Math.min(currentData.first, first);
+        currentData.last = Math.max(currentData.last, last);
+      }
+    }
+    gUndoData.set("visits", Array.from(visitMap.values()));
+  },
+
   /**
    * Cleans up references to migrators and nsIProfileInstance instances.
    */
   finishMigration: function MU_finishMigration() {
     gMigrators = null;
     gProfileStartup = null;
     gMigrationBundle = null;
   },

--- a/browser/components/migration/tests/unit/head_migration.js
+++ b/browser/components/migration/tests/unit/head_migration.js
@@ -1,25 +1,30 @@
 "use strict";
 
 /* exported gProfD, promiseMigration, registerFakePath */
 
 var { classes: Cc, interfaces: Ci, results: Cr, utils: Cu } = Components;
 
 Cu.importGlobalProperties([ "URL" ]);
 
+Cu.import("resource:///modules/MigrationUtils.jsm");
+Cu.import("resource://gre/modules/LoginHelper.jsm");
+Cu.import("resource://gre/modules/NetUtil.jsm");
+Cu.import("resource://gre/modules/PlacesUtils.jsm");
+Cu.import("resource://gre/modules/Preferences.jsm");
+Cu.import("resource://gre/modules/PromiseUtils.jsm");
+Cu.import("resource://gre/modules/Task.jsm");
+Cu.import("resource://gre/modules/Services.jsm");
 Cu.import("resource://gre/modules/XPCOMUtils.jsm");
-Cu.import("resource://gre/modules/Services.jsm");
+Cu.import("resource://testing-common/TestUtils.jsm");
+Cu.import("resource://testing-common/PlacesTestUtils.jsm");
 
-XPCOMUtils.defineLazyModuleGetter(this, "PlacesUtils",
-                                  "resource://gre/modules/PlacesUtils.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "FileUtils",
                                   "resource://gre/modules/FileUtils.jsm");
-XPCOMUtils.defineLazyModuleGetter(this, "MigrationUtils",
-                                  "resource:///modules/MigrationUtils.jsm");
 
 // Initialize profile.
 var gProfD = do_get_profile();
 
 Cu.import("resource://testing-common/AppInfo.jsm"); /* globals updateAppInfo */
 updateAppInfo();
 
 /**

--- a/browser/components/migration/tests/unit/test_automigration.js
+++ b/browser/components/migration/tests/unit/test_automigration.js
@@ -1,16 +1,10 @@
 "use strict";
 
-Cu.import("resource:///modules/MigrationUtils.jsm");
-Cu.import("resource://gre/modules/LoginHelper.jsm");
-Cu.import("resource://gre/modules/PlacesUtils.jsm");
-Cu.import("resource://gre/modules/Preferences.jsm");
-Cu.import("resource://testing-common/TestUtils.jsm");
-Cu.import("resource://testing-common/PlacesTestUtils.jsm");
 let AutoMigrateBackstage = Cu.import("resource:///modules/AutoMigrate.jsm"); /* globals AutoMigrate */
 
 let gShimmedMigratorKeyPicker = null;
 let gShimmedMigrator = null;
 
 const kUsecPerMin = 60 * 1000000;
 
 // This is really a proxy on MigrationUtils, but if we specify that directly,
@@ -28,16 +22,32 @@ AutoMigrateBackstage.MigrationUtils = ne
     return MigrationUtils[name];
   },
 });
 
 do_register_cleanup(function() {
   AutoMigrateBackstage.MigrationUtils = MigrationUtils;
 });
 
+// This should be replaced by using History.fetch with a fetchVisits option,
+// once that becomes available
+function* visitsForURL(url)
+{
+  let visitCount = 0;
+  let db = yield PlacesUtils.promiseDBConnection();
+  visitCount = yield db.execute(
+    `SELECT count(*) FROM moz_historyvisits v
+     JOIN moz_places h ON h.id = v.place_id
+     WHERE url_hash = hash(:url) AND url = :url`,
+     {url});
+  visitCount = visitCount[0].getInt64(0);
+  return visitCount;
+}
+
+
 /**
  * Test automatically picking a browser to migrate from
  */
 add_task(function* checkMigratorPicking() {
   Assert.throws(() => AutoMigrate.pickMigrator("firefox"),
                 /Can't automatically migrate from Firefox/,
                 "Should throw when explicitly picking Firefox.");
 
@@ -435,8 +445,195 @@ add_task(function* testLoginsRemovalByUn
   yield AutoMigrate._removeUnchangedLogins(undoLoginData);
   Assert.equal(0, LoginHelper.searchLoginsWithObject({hostname: "https://example.com", formSubmitURL: "https://example.com/"}).length,
                    "unchanged example.com entry should have been removed.");
   Assert.equal(1, LoginHelper.searchLoginsWithObject({hostname: "https://example.org", formSubmitURL: "https://example.org/"}).length,
                    "changed example.org entry should have persisted.");
   Services.logins.removeAllLogins();
 });
 
+add_task(function* checkUndoVisitsState() {
+  MigrationUtils.initializeUndoData();
+  yield MigrationUtils.insertVisitsWrapper([{
+    uri: NetUtil.newURI("http://www.example.com/"),
+    title: "Example",
+    visits: [{
+      visitDate: new Date("2015-07-10").getTime() * 1000,
+      transitionType: Ci.nsINavHistoryService.TRANSITION_LINK,
+    }, {
+      visitDate: new Date("2015-09-10").getTime() * 1000,
+      transitionType: Ci.nsINavHistoryService.TRANSITION_LINK,
+    }, {
+      visitDate: new Date("2015-08-10").getTime() * 1000,
+      transitionType: Ci.nsINavHistoryService.TRANSITION_LINK,
+    }],
+  }, {
+    uri: NetUtil.newURI("http://www.example.org/"),
+    title: "Example",
+    visits: [{
+      visitDate: new Date("2016-04-03").getTime() * 1000,
+      transitionType: Ci.nsINavHistoryService.TRANSITION_LINK,
+    }, {
+      visitDate: new Date("2015-08-03").getTime() * 1000,
+      transitionType: Ci.nsINavHistoryService.TRANSITION_LINK,
+    }],
+  }, {
+    uri: NetUtil.newURI("http://www.example.com/"),
+    title: "Example",
+    visits: [{
+      visitDate: new Date("2015-10-10").getTime() * 1000,
+      transitionType: Ci.nsINavHistoryService.TRANSITION_LINK,
+    }],
+  }]);
+  let undoVisitData = (yield MigrationUtils.stopAndRetrieveUndoData()).get("visits");
+  Assert.deepEqual(Array.from(undoVisitData.map(v => v.url)).sort(),
+                   ["http://www.example.com/", "http://www.example.org/"]);
+  Assert.deepEqual(undoVisitData.find(v => v.url == "http://www.example.com/"), {
+    url: "http://www.example.com/",
+    visitCount: 4,
+    first: new Date("2015-07-10").getTime() * 1000,
+    last: new Date("2015-10-10").getTime() * 1000,
+  });
+  Assert.deepEqual(undoVisitData.find(v => v.url == "http://www.example.org/"), {
+    url: "http://www.example.org/",
+    visitCount: 2,
+    first: new Date("2015-08-03").getTime() * 1000,
+    last: new Date("2016-04-03").getTime() * 1000,
+  });
+
+  yield PlacesTestUtils.clearHistory();
+});
+
+add_task(function* checkUndoVisitsState() {
+  MigrationUtils.initializeUndoData();
+  yield MigrationUtils.insertVisitsWrapper([{
+    uri: NetUtil.newURI("http://www.example.com/"),
+    title: "Example",
+    visits: [{
+      visitDate: new Date("2015-07-10").getTime() * 1000,
+      transitionType: Ci.nsINavHistoryService.TRANSITION_LINK,
+    }, {
+      visitDate: new Date("2015-09-10").getTime() * 1000,
+      transitionType: Ci.nsINavHistoryService.TRANSITION_LINK,
+    }, {
+      visitDate: new Date("2015-08-10").getTime() * 1000,
+      transitionType: Ci.nsINavHistoryService.TRANSITION_LINK,
+    }],
+  }, {
+    uri: NetUtil.newURI("http://www.example.org/"),
+    title: "Example",
+    visits: [{
+      visitDate: new Date("2016-04-03").getTime() * 1000,
+      transitionType: Ci.nsINavHistoryService.TRANSITION_LINK,
+    }, {
+      visitDate: new Date("2015-08-03").getTime() * 1000,
+      transitionType: Ci.nsINavHistoryService.TRANSITION_LINK,
+    }],
+  }, {
+    uri: NetUtil.newURI("http://www.example.com/"),
+    title: "Example",
+    visits: [{
+      visitDate: new Date("2015-10-10").getTime() * 1000,
+      transitionType: Ci.nsINavHistoryService.TRANSITION_LINK,
+    }],
+  }, {
+    uri: NetUtil.newURI("http://www.mozilla.org/"),
+    title: "Example",
+    visits: [{
+      visitDate: new Date("2015-01-01").getTime() * 1000,
+      transitionType: Ci.nsINavHistoryService.TRANSITION_LINK,
+    }],
+  }]);
+
+  // We have to wait until frecency updates have been handled in order
+  // to accurately determine whether we're doing the right thing.
+  let frecencyUpdatesHandled = new Promise(resolve => {
+    PlacesUtils.history.addObserver({
+      onFrecencyChanged(aURI) {
+        if (aURI.spec == "http://www.unrelated.org/") {
+          PlacesUtils.history.removeObserver(this);
+          resolve();
+        }
+      }
+    }, false);
+  });
+  yield PlacesUtils.history.insertMany([{
+    url: "http://www.example.com/",
+    title: "Example",
+    visits: [{
+      date: new Date("2015-08-16"),
+    }],
+  }, {
+    url: "http://www.example.org/",
+    title: "Example",
+    visits: [{
+      date: new Date("2016-01-03"),
+    }, {
+      date: new Date("2015-05-03"),
+    }],
+  }, {
+    url: "http://www.unrelated.org/",
+    title: "Unrelated",
+    visits: [{
+      date: new Date("2015-09-01"),
+    }],
+  }]);
+  yield frecencyUpdatesHandled;
+  let undoVisitData = (yield MigrationUtils.stopAndRetrieveUndoData()).get("visits");
+
+  let frecencyChangesExpected = new Map([
+    ["http://www.example.com/", PromiseUtils.defer()],
+    ["http://www.example.org/", PromiseUtils.defer()]
+  ]);
+  let uriDeletedExpected = new Map([
+    ["http://www.mozilla.org/", PromiseUtils.defer()],
+  ]);
+  let wrongMethodDeferred = PromiseUtils.defer();
+  let observer = {
+    onBeginUpdateBatch: function() {},
+    onEndUpdateBatch: function() {},
+    onVisit: function(uri) {
+      wrongMethodDeferred.reject(new Error("Unexpected call to onVisit " + uri.spec));
+    },
+    onTitleChanged: function(uri) {
+      wrongMethodDeferred.reject(new Error("Unexpected call to onTitleChanged " + uri.spec));
+    },
+    onClearHistory: function() {
+      wrongMethodDeferred.reject("Unexpected call to onClearHistory");
+    },
+    onPageChanged: function(uri) {
+      wrongMethodDeferred.reject(new Error("Unexpected call to onPageChanged " + uri.spec));
+    },
+    onFrecencyChanged: function(aURI) {
+      do_print("frecency change");
+      Assert.ok(frecencyChangesExpected.has(aURI.spec),
+                "Should be expecting frecency change for " + aURI.spec);
+      frecencyChangesExpected.get(aURI.spec).resolve();
+    },
+    onManyFrecenciesChanged: function() {
+      do_print("Many frecencies changed");
+      wrongMethodDeferred.reject(new Error("This test can't deal with onManyFrecenciesChanged to be called"));
+    },
+    onDeleteURI: function(aURI) {
+      do_print("delete uri");
+      Assert.ok(uriDeletedExpected.has(aURI.spec),
+                "Should be expecting uri deletion for " + aURI.spec);
+      uriDeletedExpected.get(aURI.spec).resolve();
+    },
+  };
+  PlacesUtils.history.addObserver(observer, false);
+
+  yield AutoMigrate._removeSomeVisits(undoVisitData);
+  PlacesUtils.history.removeObserver(observer);
+  yield Promise.all(uriDeletedExpected.values());
+  yield Promise.all(frecencyChangesExpected.values());
+
+  Assert.equal(yield visitsForURL("http://www.example.com/"), 1,
+               "1 example.com visit (out of 5) should have persisted despite being within the range, due to limiting");
+  Assert.equal(yield visitsForURL("http://www.mozilla.org/"), 0,
+               "0 mozilla.org visits should have persisted (out of 1).");
+  Assert.equal(yield visitsForURL("http://www.example.org/"), 2,
+               "2 example.org visits should have persisted (out of 4).");
+  Assert.equal(yield visitsForURL("http://www.unrelated.org/"), 1,
+               "1 unrelated.org visits should have persisted as it's not involved in the import.");
+  yield PlacesTestUtils.clearHistory();
+});
+