--- a/toolkit/components/places/History.jsm
+++ b/toolkit/components/places/History.jsm
@@ -85,16 +85,20 @@ Cu.importGlobalProperties(["URL"]);
  * Whenever we update or remove numerous pages, it is preferable
  * to yield time to the main thread every so often to avoid janking.
  * These constants determine the maximal number of notifications we
  * may emit before we yield.
  */
 const NOTIFICATION_CHUNK_SIZE = 300;
 const ONRESULT_CHUNK_SIZE = 300;
 
+// This constant determines the maximum number of remove pages before we cycle.
+const REMOVE_PAGES_CHUNKLEN = 300;
+
+
 // Timers resolution is not always good, it can have a 16ms precision on Win.
 const TIMERS_RESOLUTION_SKEW_MS = 16;
 
 /**
  * Sends a bookmarks notification through the given observers.
  *
  * @param observers
  *        array of nsINavBookmarkObserver objects.
@@ -294,27 +298,50 @@ this.History = Object.freeze({
       // be normalized.
       let normalized = normalizeToURLOrGUID(page);
       if (typeof normalized === "string") {
         guids.push(normalized);
       } else {
         urls.push(normalized.href);
       }
     }
-    let normalizedPages = {guids, urls};
 
     // At this stage, we know that either `guids` is not-empty
     // or `urls` is not-empty.
 
     if (onResult && typeof onResult != "function") {
       throw new TypeError("Invalid function: " + onResult);
     }
 
-    return PlacesUtils.withConnectionWrapper("History.jsm: remove",
-      db => remove(db, normalizedPages, onResult));
+    return Task.spawn(function* () {
+      let removedPages = false;
+      let count = 0;
+      while (guids.length || urls.length) {
+        if (count && count % 2 == 0) {
+          // Every few cycles, yield time back to the main
+          // thread to avoid jank.
+          yield Promise.resolve();
+        }
+        count++;
+        let guidsSlice = guids.splice(0, REMOVE_PAGES_CHUNKLEN);
+        let urlsSlice = [];
+        if (guidsSlice.length < REMOVE_PAGES_CHUNKLEN) {
+          urlsSlice = urls.splice(0, REMOVE_PAGES_CHUNKLEN - guidsSlice.length);
+        }
+
+        let pages = {guids: guidsSlice, urls: urlsSlice};
+
+        let result =
+          yield PlacesUtils.withConnectionWrapper("History.jsm: remove",
+                                                  db => remove(db, pages, onResult));
+
+        removedPages = removedPages || result;
+      }
+      return removedPages;
+    });
   },
 
   /**
    * Remove visits matching specific characteristics.
    *
    * Any change may be observed through nsINavHistoryObserver.
    *
    * @param filter: (object)

--- a/toolkit/components/places/tests/history/test_remove.js
+++ b/toolkit/components/places/tests/history/test_remove.js
@@ -130,151 +130,16 @@ add_task(function* test_remove_single() 
         yield remover("Testing History.remove() with a single string guid in an array", x => [do_get_guid_for_uri(x)], options);
       }
     }
   } finally {
     yield PlacesTestUtils.clearHistory();
   }
 });
 
-// Test removing a list of pages
-add_task(function* test_remove_many() {
-  const SIZE = 10;
-
-  yield PlacesTestUtils.clearHistory();
-  yield PlacesUtils.bookmarks.eraseEverything();
-
-  do_print("Adding a witness page");
-  let WITNESS_URI = NetUtil.newURI("http://mozilla.com/test_browserhistory/test_remove/" + Math.random());
-  yield PlacesTestUtils.addVisits(WITNESS_URI);
-  Assert.ok(page_in_database(WITNESS_URI), "Witness page added");
-
-  do_print("Generating samples");
-  let pages = [];
-  for (let i = 0; i < SIZE; ++i) {
-    let uri = NetUtil.newURI("http://mozilla.com/test_browserhistory/test_remove?sample=" + i + "&salt=" + Math.random());
-    let title = "Visit " + i + ", " + Math.random();
-    let hasBookmark = i % 3 == 0;
-    let page = {
-      uri,
-      title,
-      hasBookmark,
-      // `true` once `onResult` has been called for this page
-      onResultCalled: false,
-      // `true` once `onDeleteVisits` has been called for this page
-      onDeleteVisitsCalled: false,
-      // `true` once `onFrecencyChangedCalled` has been called for this page
-      onFrecencyChangedCalled: false,
-      // `true` once `onDeleteURI` has been called for this page
-      onDeleteURICalled: false,
-    };
-    do_print("Pushing: " + uri.spec);
-    pages.push(page);
-
-    yield PlacesTestUtils.addVisits(page);
-    page.guid = do_get_guid_for_uri(uri);
-    if (hasBookmark) {
-      PlacesUtils.bookmarks.insertBookmark(
-        PlacesUtils.unfiledBookmarksFolderId,
-        uri,
-        PlacesUtils.bookmarks.DEFAULT_INDEX,
-        "test bookmark " + i);
-    }
-    Assert.ok(page_in_database(uri), "Page added");
-  }
-
-  do_print("Mixing key types and introducing dangling keys");
-  let keys = [];
-  for (let i = 0; i < SIZE; ++i) {
-    if (i % 4 == 0) {
-      keys.push(pages[i].uri);
-      keys.push(NetUtil.newURI("http://example.org/dangling/nsIURI/" + i));
-    } else if (i % 4 == 1) {
-      keys.push(new URL(pages[i].uri.spec));
-      keys.push(new URL("http://example.org/dangling/URL/" + i));
-    } else if (i % 4 == 2) {
-      keys.push(pages[i].uri.spec);
-      keys.push("http://example.org/dangling/stringuri/" + i);
-    } else {
-      keys.push(pages[i].guid);
-      keys.push(("guid_" + i + "_01234567890").substr(0, 12));
-    }
-  }
-
-  let observer = {
-    onBeginUpdateBatch() {},
-    onEndUpdateBatch() {},
-    onVisit(aURI) {
-      Assert.ok(false, "Unexpected call to onVisit " + aURI.spec);
-    },
-    onTitleChanged(aURI) {
-      Assert.ok(false, "Unexpected call to onTitleChanged " + aURI.spec);
-    },
-    onClearHistory() {
-      Assert.ok(false, "Unexpected call to onClearHistory");
-    },
-    onPageChanged(aURI) {
-      Assert.ok(false, "Unexpected call to onPageChanged " + aURI.spec);
-    },
-    onFrecencyChanged(aURI) {
-      let origin = pages.find(x => x.uri.spec == aURI.spec);
-      Assert.ok(origin);
-      Assert.ok(origin.hasBookmark, "Observing onFrecencyChanged on a page with a bookmark");
-      origin.onFrecencyChangedCalled = true;
-      // We do not make sure that `origin.onFrecencyChangedCalled` is `false`, as
-    },
-    onManyFrecenciesChanged() {
-      Assert.ok(false, "Observing onManyFrecenciesChanges, this is most likely correct but not covered by this test");
-    },
-    onDeleteURI(aURI) {
-      let origin = pages.find(x => x.uri.spec == aURI.spec);
-      Assert.ok(origin);
-      Assert.ok(!origin.hasBookmark, "Observing onDeleteURI on a page without a bookmark");
-      Assert.ok(!origin.onDeleteURICalled, "Observing onDeleteURI for the first time");
-      origin.onDeleteURICalled = true;
-    },
-    onDeleteVisits(aURI) {
-      let origin = pages.find(x => x.uri.spec == aURI.spec);
-      Assert.ok(origin);
-      Assert.ok(!origin.onDeleteVisitsCalled, "Observing onDeleteVisits for the first time");
-      origin.onDeleteVisitsCalled = true;
-    }
-  };
-  PlacesUtils.history.addObserver(observer);
-
-  do_print("Removing the pages and checking the callbacks");
-  let removed = yield PlacesUtils.history.remove(keys, page => {
-    let origin = pages.find(candidate => candidate.uri.spec == page.url.href);
-
-    Assert.ok(origin, "onResult has a valid page");
-    Assert.ok(!origin.onResultCalled, "onResult has not seen this page yet");
-    origin.onResultCalled = true;
-    Assert.equal(page.guid, origin.guid, "onResult has the right guid");
-    Assert.equal(page.title, origin.title, "onResult has the right title");
-  });
-  Assert.ok(removed, "Something was removed");
-
-  PlacesUtils.history.removeObserver(observer);
-
-  do_print("Checking out results");
-  // By now the observers should have been called.
-  for (let i = 0; i < pages.length; ++i) {
-    let page = pages[i];
-    do_print("Page: " + i);
-    Assert.ok(page.onResultCalled, "We have reached the page from the callback");
-    Assert.ok(visits_in_database(page.uri) == 0, "History entry has disappeared");
-    Assert.equal(page_in_database(page.uri) != 0, page.hasBookmark, "Page is present only if it also has bookmarks");
-    Assert.equal(page.onFrecencyChangedCalled, page.onDeleteVisitsCalled, "onDeleteVisits was called iff onFrecencyChanged was called");
-    Assert.ok(page.onFrecencyChangedCalled ^ page.onDeleteURICalled, "Either onFrecencyChanged or onDeleteURI was called");
-  }
-
-  Assert.notEqual(visits_in_database(WITNESS_URI), 0, "Witness URI still has visits");
-  Assert.notEqual(page_in_database(WITNESS_URI), 0, "Witness URI is still here");
-});
-
 add_task(function* cleanup() {
   yield PlacesTestUtils.clearHistory();
   yield PlacesUtils.bookmarks.eraseEverything();
 });
 
 // Test the various error cases
 add_task(function* test_error_cases() {
   Assert.throws(

new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/tests/history/test_removeMany.js
@@ -0,0 +1,149 @@
+/* -*- indent-tabs-mode: nil; js-indent-level: 2 -*- */
+/* vim:set ts=2 sw=2 sts=2 et: */
+
+// Tests for `History.remove` with removing many urls, as implemented in
+// History.jsm.
+
+"use strict";
+
+// Test removing a list of pages
+add_task(function* test_remove_many() {
+  // This is set so that we are guarenteed to trigger REMOVE_PAGES_CHUNKLEN.
+  const SIZE = 1000;
+
+  yield PlacesTestUtils.clearHistory();
+  yield PlacesUtils.bookmarks.eraseEverything();
+
+  do_print("Adding a witness page");
+  let WITNESS_URI = NetUtil.newURI("http://mozilla.com/test_browserhistory/test_remove/" + Math.random());
+  yield PlacesTestUtils.addVisits(WITNESS_URI);
+  Assert.ok(page_in_database(WITNESS_URI), "Witness page added");
+
+  do_print("Generating samples");
+  let pages = [];
+  for (let i = 0; i < SIZE; ++i) {
+    let uri = NetUtil.newURI("http://mozilla.com/test_browserhistory/test_remove?sample=" + i + "&salt=" + Math.random());
+    let title = "Visit " + i + ", " + Math.random();
+    let hasBookmark = i % 3 == 0;
+    let page = {
+      uri,
+      title,
+      hasBookmark,
+      // `true` once `onResult` has been called for this page
+      onResultCalled: false,
+      // `true` once `onDeleteVisits` has been called for this page
+      onDeleteVisitsCalled: false,
+      // `true` once `onFrecencyChangedCalled` has been called for this page
+      onFrecencyChangedCalled: false,
+      // `true` once `onDeleteURI` has been called for this page
+      onDeleteURICalled: false,
+    };
+    do_print("Pushing: " + uri.spec);
+    pages.push(page);
+
+    yield PlacesTestUtils.addVisits(page);
+    page.guid = do_get_guid_for_uri(uri);
+    if (hasBookmark) {
+      PlacesUtils.bookmarks.insertBookmark(
+        PlacesUtils.unfiledBookmarksFolderId,
+        uri,
+        PlacesUtils.bookmarks.DEFAULT_INDEX,
+        "test bookmark " + i);
+    }
+    Assert.ok(page_in_database(uri), "Page added");
+  }
+
+  do_print("Mixing key types and introducing dangling keys");
+  let keys = [];
+  for (let i = 0; i < SIZE; ++i) {
+    if (i % 4 == 0) {
+      keys.push(pages[i].uri);
+      keys.push(NetUtil.newURI("http://example.org/dangling/nsIURI/" + i));
+    } else if (i % 4 == 1) {
+      keys.push(new URL(pages[i].uri.spec));
+      keys.push(new URL("http://example.org/dangling/URL/" + i));
+    } else if (i % 4 == 2) {
+      keys.push(pages[i].uri.spec);
+      keys.push("http://example.org/dangling/stringuri/" + i);
+    } else {
+      keys.push(pages[i].guid);
+      keys.push(("guid_" + i + "_01234567890").substr(0, 12));
+    }
+  }
+
+  let observer = {
+    onBeginUpdateBatch() {},
+    onEndUpdateBatch() {},
+    onVisit(aURI) {
+      Assert.ok(false, "Unexpected call to onVisit " + aURI.spec);
+    },
+    onTitleChanged(aURI) {
+      Assert.ok(false, "Unexpected call to onTitleChanged " + aURI.spec);
+    },
+    onClearHistory() {
+      Assert.ok(false, "Unexpected call to onClearHistory");
+    },
+    onPageChanged(aURI) {
+      Assert.ok(false, "Unexpected call to onPageChanged " + aURI.spec);
+    },
+    onFrecencyChanged(aURI) {
+      let origin = pages.find(x => x.uri.spec == aURI.spec);
+      Assert.ok(origin);
+      Assert.ok(origin.hasBookmark, "Observing onFrecencyChanged on a page with a bookmark");
+      origin.onFrecencyChangedCalled = true;
+    },
+    onManyFrecenciesChanged() {
+      Assert.ok(false, "Observing onManyFrecenciesChanges, this is most likely correct but not covered by this test");
+    },
+    onDeleteURI(aURI) {
+      let origin = pages.find(x => x.uri.spec == aURI.spec);
+      Assert.ok(origin);
+      Assert.ok(!origin.hasBookmark, "Observing onDeleteURI on a page without a bookmark");
+      Assert.ok(!origin.onDeleteURICalled, "Observing onDeleteURI for the first time");
+      origin.onDeleteURICalled = true;
+    },
+    onDeleteVisits(aURI) {
+      let origin = pages.find(x => x.uri.spec == aURI.spec);
+      Assert.ok(origin);
+      Assert.ok(!origin.onDeleteVisitsCalled, "Observing onDeleteVisits for the first time");
+      origin.onDeleteVisitsCalled = true;
+    }
+  };
+  PlacesUtils.history.addObserver(observer);
+
+  do_print("Removing the pages and checking the callbacks");
+
+  let removed = yield PlacesUtils.history.remove(keys, page => {
+    let origin = pages.find(candidate => candidate.uri.spec == page.url.href);
+
+    Assert.ok(origin, "onResult has a valid page");
+    Assert.ok(!origin.onResultCalled, "onResult has not seen this page yet");
+    origin.onResultCalled = true;
+    Assert.equal(page.guid, origin.guid, "onResult has the right guid");
+    Assert.equal(page.title, origin.title, "onResult has the right title");
+  });
+
+  Assert.ok(removed, "Something was removed");
+
+  PlacesUtils.history.removeObserver(observer);
+
+  do_print("Checking out results");
+  // By now the observers should have been called.
+  for (let i = 0; i < pages.length; ++i) {
+    let page = pages[i];
+    do_print("Page: " + i);
+    Assert.ok(page.onResultCalled, "We have reached the page from the callback");
+    Assert.ok(visits_in_database(page.uri) == 0, "History entry has disappeared");
+    Assert.equal(page_in_database(page.uri) != 0, page.hasBookmark, "Page is present only if it also has bookmarks");
+    Assert.equal(page.onFrecencyChangedCalled, page.onDeleteVisitsCalled, "onDeleteVisits was called iff onFrecencyChanged was called");
+    Assert.ok(page.onFrecencyChangedCalled ^ page.onDeleteURICalled, "Either onFrecencyChanged or onDeleteURI was called");
+  }
+
+  Assert.notEqual(visits_in_database(WITNESS_URI), 0, "Witness URI still has visits");
+  Assert.notEqual(page_in_database(WITNESS_URI), 0, "Witness URI is still here");
+});
+
+add_task(function* cleanup() {
+  yield PlacesTestUtils.clearHistory();
+  yield PlacesUtils.bookmarks.eraseEverything();
+});

--- a/toolkit/components/places/tests/history/xpcshell.ini
+++ b/toolkit/components/places/tests/history/xpcshell.ini
@@ -1,11 +1,12 @@
 [DEFAULT]
 head = head_history.js
 
 [test_async_history_api.js]
 [test_insert.js]
 [test_insertMany.js]
 [test_remove.js]
+[test_removeMany.js]
 [test_removeVisits.js]
 [test_removeVisitsByFilter.js]
 [test_sameUri_titleChanged.js]
 [test_updatePlaces_embed.js]