--- a/services/sync/modules/engines/history.js
+++ b/services/sync/modules/engines/history.js
@@ -92,16 +92,20 @@ function HistoryStore(name, engine) {
     }
     this._stmts = {};
   }, this);
 }
 HistoryStore.prototype = {
   __proto__: Store.prototype,
 
   __asyncHistory: null,
+
+  // We try and only update this many visits at one time.
+  MAX_VISITS_PER_INSERT: 500,
+
   get _asyncHistory() {
     if (!this.__asyncHistory) {
       this.__asyncHistory = Cc["@mozilla.org/browser/history;1"]
                               .getService(Ci.mozIAsyncHistory);
     }
     return this.__asyncHistory;
   },
 
@@ -207,23 +211,58 @@ HistoryStore.prototype = {
 
       if (shouldApply) {
         k += 1;
       }
     }
     records.length = k; // truncate array
 
     if (records.length) {
-      await PlacesUtils.history.insertMany(records);
+      for (let chunk of this._generateChunks(records)) {
+        await PlacesUtils.history.insertMany(chunk);
+      }
     }
 
     return failed;
   },
 
   /**
+   * Returns a generator that splits records into sanely sized chunks suitable
+   * for passing to places to prevent places doing bad things at shutdown.
+   */
+  * _generateChunks(records) {
+    // We chunk based on the number of *visits* inside each record. However,
+    // we do not split a single record into multiple records, because at some
+    // time in the future, we intend to ensure these records are ordered by
+    // lastModified, and advance the engine's timestamp as we process them,
+    // meaning we can resume exactly where we left off next sync - although
+    // currently that's not done, so we will retry the entire batch next sync
+    // if interrupted.
+    // ie, this means that if a single record has more than MAX_VISITS_PER_INSERT
+    // visits, we will call insertMany() with exactly 1 record, but with
+    // more than MAX_VISITS_PER_INSERT visits.
+    let curIndex = 0;
+    this._log.debug(`adding ${records.length} records to history`);
+    while (curIndex < records.length) {
+      Async.checkAppReady(); // may throw if we are shutting down.
+      let toAdd = []; // what we are going to insert.
+      let count = 0; // a counter which tells us when toAdd is full.
+      do {
+        let record = records[curIndex];
+        curIndex += 1;
+        toAdd.push(record);
+        count += record.visits.length;
+      } while (curIndex < records.length &&
+               count + records[curIndex].visits.length <= this.MAX_VISITS_PER_INSERT);
+      this._log.trace(`adding ${toAdd.length} items in this chunk`);
+      yield toAdd;
+    }
+  },
+
+  /**
    * Converts a Sync history record to a mozIPlaceInfo.
    *
    * Throws if an invalid record is encountered (invalid URI, etc.),
    * returns true if the record is to be applied, false otherwise
    * (no visits to add, etc.),
    */
   async _recordToPlaceInfo(record) {
     // Sort out invalid URIs and ones Places just simply doesn't want.

--- a/services/sync/tests/unit/test_history_store.js
+++ b/services/sync/tests/unit/test_history_store.js
@@ -338,12 +338,76 @@ add_task(async function test_remove() {
   });
   do_check_null(queryres);
   queryres = await PlacesUtils.history.fetch(tburi.spec, {
     includeVisits: true,
   });
   do_check_null(queryres);
 });
 
+add_task(async function test_chunking() {
+  let mvpi = store.MAX_VISITS_PER_INSERT;
+  store.MAX_VISITS_PER_INSERT = 3;
+  let checkChunks = function(input, expected) {
+    let chunks = Array.from(store._generateChunks(input));
+    deepEqual(chunks, expected);
+  };
+  try {
+    checkChunks([{visits: ["x"]}],
+                [[{visits: ["x"]}]]);
+
+    // 3 should still be one chunk.
+    checkChunks([{visits: ["x", "x", "x"]}],
+                [[{visits: ["x", "x", "x"]}]]);
+
+    // 4 should still be one chunk as we don't split individual records.
+    checkChunks([{visits: ["x", "x", "x", "x"]}],
+                [[{visits: ["x", "x", "x", "x"]}]]
+               );
+
+    // 4 in the first and 1 in the second should be 2 chunks.
+    checkChunks([
+                  {visits: ["x", "x", "x", "x"]},
+                  {visits: ["x"]}
+                ],
+                // expected
+                [
+                  [
+                    {visits: ["x", "x", "x", "x"]}
+                  ],
+                  [
+                    {visits: ["x"]}
+                  ],
+                ]
+               );
+
+    // we put multiple records into chunks
+    checkChunks([
+                  {visits: ["x", "x"]},
+                  {visits: ["x"]},
+                  {visits: ["x"]},
+                  {visits: ["x", "x"]},
+                  {visits: ["x", "x", "x", "x"]},
+                ],
+                // expected
+                [
+                  [
+                    {visits: ["x", "x"]},
+                    {visits: ["x"]},
+                  ],
+                  [
+                    {visits: ["x"]},
+                    {visits: ["x", "x"]},
+                  ],
+                  [
+                    {visits: ["x", "x", "x", "x"]},
+                  ],
+                ]
+               );
+  } finally {
+    store.MAX_VISITS_PER_INSERT = mvpi;
+  }
+});
+
 add_task(async function cleanup() {
   _("Clean up.");
   await PlacesTestUtils.clearHistory();
 });