--- a/browser/components/places/content/controller.js
+++ b/browser/components/places/content/controller.js
@@ -840,17 +840,17 @@ PlacesController.prototype = {
         // History deletes are not undoable, so we don't have a transaction.
       } else if (node.itemId == -1 &&
                PlacesUtils.nodeIsQuery(node) &&
                PlacesUtils.asQuery(node).queryOptions.queryType ==
                  Ci.nsINavHistoryQueryOptions.QUERY_TYPE_HISTORY) {
         // This is a dynamically generated history query, like queries
         // grouped by site, time or both.  Dynamically generated queries don't
         // have an itemId even if they are descendants of a bookmark.
-        this._removeHistoryContainer(node);
+        await this._removeHistoryContainer(node);
         // History deletes are not undoable, so we don't have a transaction.
       } else {
         // This is a common bookmark item.
         if (PlacesUtils.nodeIsFolder(node)) {
           // If this is a folder we add it to our array of folders, used
           // to skip nodes that are children of an already removed folder.
           removedFolders.push(node);
         }
@@ -885,56 +885,61 @@ PlacesController.prototype = {
     }
   },
 
   /**
    * Removes the set of selected ranges from history, asynchronously.
    *
    * @note history deletes are not undoable.
    */
-  _removeRowsFromHistory: function PC__removeRowsFromHistory() {
+  async _removeRowsFromHistory() {
     let nodes = this._view.selectedNodes;
     let URIs = new Set();
     for (let i = 0; i < nodes.length; ++i) {
       let node = nodes[i];
       if (PlacesUtils.nodeIsURI(node)) {
         URIs.add(node.uri);
       } else if (PlacesUtils.nodeIsQuery(node) &&
                PlacesUtils.asQuery(node).queryOptions.queryType ==
                  Ci.nsINavHistoryQueryOptions.QUERY_TYPE_HISTORY) {
-        this._removeHistoryContainer(node);
+        await this._removeHistoryContainer(node);
       }
     }
 
-    PlacesUtils.history.remove([...URIs]).catch(Components.utils.reportError);
+    await PlacesUtils.history.remove([...URIs]);
   },
 
   /**
    * Removes history visits for an history container node.
    * @param   [in] aContainerNode
    *          The container node to remove.
    *
    * @note history deletes are not undoable.
    */
   _removeHistoryContainer: function PC__removeHistoryContainer(aContainerNode) {
     if (PlacesUtils.nodeIsHost(aContainerNode)) {
       // Site container.
-      PlacesUtils.history.removePagesFromHost(aContainerNode.title, true);
+      PlacesUtils.history.removeByFilter({
+        host: "*." + aContainerNode.title
+      });
     } else if (PlacesUtils.nodeIsDay(aContainerNode)) {
       // Day container.
       let query = aContainerNode.getQueries()[0];
       let beginTime = query.beginTime;
       let endTime = query.endTime;
       NS_ASSERT(query && beginTime && endTime,
                 "A valid date container query should exist!");
       // We want to exclude beginTime from the removal because
       // removePagesByTimeframe includes both extremes, while date containers
       // exclude the lower extreme.  So, if we would not exclude it, we would
       // end up removing more history than requested.
-      PlacesUtils.history.removePagesByTimeframe(beginTime + 1, endTime);
+      PlacesUtils.history.removeByFilter({
+        beginDate: PlacesUtils.toDate(beginTime + 1000),
+        endDate: PlacesUtils.toDate(endTime)
+      });
     }
   },
 
   /**
    * Removes the selection
    * @param   aTxnName
    *          A name for the transaction if this is being performed
    *          as part of another operation.
@@ -949,17 +954,17 @@ PlacesController.prototype = {
 
     if (PlacesUtils.nodeIsFolder(root)) {
       await this._removeRowsFromBookmarks(aTxnName);
     } else if (PlacesUtils.nodeIsQuery(root)) {
       var queryType = PlacesUtils.asQuery(root).queryOptions.queryType;
       if (queryType == Ci.nsINavHistoryQueryOptions.QUERY_TYPE_BOOKMARKS) {
         await this._removeRowsFromBookmarks(aTxnName);
       } else if (queryType == Ci.nsINavHistoryQueryOptions.QUERY_TYPE_HISTORY) {
-        this._removeRowsFromHistory();
+        await this._removeRowsFromHistory();
       } else {
         NS_ASSERT(false, "implement support for QUERY_TYPE_UNIFIED");
       }
     } else
       NS_ASSERT(false, "unexpected root");
   },
 
   /**

--- a/services/sync/tps/extensions/tps/resource/modules/history.jsm
+++ b/services/sync/tps/extensions/tps/resource/modules/history.jsm
@@ -127,17 +127,17 @@ var HistoryEntry = {
    */
   async Delete(item, usSinceEpoch) {
     if ("uri" in item) {
       let removedAny = await PlacesUtils.history.remove(item.uri);
       if (!removedAny) {
         Logger.log("Warning: Removed 0 history visits for uri " + item.uri);
       }
     } else if ("host" in item) {
-      await PlacesUtils.history.removePagesFromHost(item.host, false);
+      await PlacesUtils.history.removeByFilter({ host: item.host });
     } else if ("begin" in item && "end" in item) {
       let msSinceEpoch = parseInt(usSinceEpoch / 1000);
       let filter = {
         beginDate: new Date(msSinceEpoch + (item.begin * 60 * 60 * 1000)),
         endDate: new Date(msSinceEpoch + (item.end * 60 * 60 * 1000))
       };
       let removedAny = await PlacesUtils.history.removeVisitsByFilter(filter);
       if (!removedAny) {

--- a/toolkit/components/places/tests/favicons/test_root_icons.js
+++ b/toolkit/components/places/tests/favicons/test_root_icons.js
@@ -60,33 +60,36 @@ add_task(async function test_removePages
   // Sanity checks.
   Assert.equal(await getFaviconUrlForPage(pageURI),
                faviconURI.spec, "Should get the biggest icon");
   Assert.equal(await getFaviconUrlForPage(pageURI, 1),
                rootIconURI.spec, "Should get the smallest icon");
   Assert.equal(await getFaviconUrlForPage("http://www.places.test/old/"),
                rootIconURI.spec, "Should get the root icon");
 
-  PlacesUtils.history.removePagesByTimeframe(
-    PlacesUtils.toPRTime(Date.now() - 14400000),
-    PlacesUtils.toPRTime(new Date())
-  );
+  await PlacesUtils.history.removeByFilter({
+    beginDate: new Date(Date.now() - 14400000),
+    endDate: new Date()
+  });
 
   // Check database entries.
   await PlacesTestUtils.promiseAsyncUpdates();
   let db = await PlacesUtils.promiseDBConnection();
   let rows = await db.execute("SELECT * FROM moz_icons");
   Assert.equal(rows.length, 1, "There should only be 1 icon entry");
   Assert.equal(rows[0].getResultByName("root"), 1, "It should be marked as a root icon");
   rows = await db.execute("SELECT * FROM moz_pages_w_icons");
   Assert.equal(rows.length, 0, "There should be no page entry");
   rows = await db.execute("SELECT * FROM moz_icons_to_pages");
   Assert.equal(rows.length, 0, "There should be no relation entry");
 
-  PlacesUtils.history.removePagesByTimeframe(0, PlacesUtils.toPRTime(new Date()));
+  await PlacesUtils.history.removeByFilter({
+    beginDate: new Date(0),
+    endDt: new Date()
+  });
   await PlacesTestUtils.promiseAsyncUpdates();
   rows = await db.execute("SELECT * FROM moz_icons");
   // Debug logging for possible intermittent failure (bug 1358368).
   if (rows.length != 0) {
     dump_table("moz_icons");
     dump_table("moz_hosts");
   }
   Assert.equal(rows.length, 0, "There should be no icon entry");

--- a/toolkit/components/places/tests/unit/test_415757.js
+++ b/toolkit/components/places/tests/unit/test_415757.js
@@ -57,17 +57,17 @@ add_task(async function test_execute() {
   var testAnnoRetainedName = "foo";
   var testAnnoRetainedValue = "bar";
   PlacesUtils.annotations.setPageAnnotation(testAnnoRetainedURI,
                                             testAnnoRetainedName,
                                             testAnnoRetainedValue, 0,
                                             PlacesUtils.annotations.EXPIRE_WITH_HISTORY);
 
   // remove pages from www.test.com
-  PlacesUtils.history.removePagesFromHost("www.test.com", false);
+  await PlacesUtils.history.removeByFilter({ host: "www.test.com" });
 
   // check that all pages in www.test.com have been removed
   for (let i = 0; i < TOTAL_SITES; i++) {
     let site = "http://www.test.com/" + i + "/";
     let testURI = uri(site);
     Assert.ok(!uri_in_db(testURI));
   }
 

--- a/toolkit/components/places/tests/unit/test_browserhistory.js
+++ b/toolkit/components/places/tests/unit/test_browserhistory.js
@@ -69,38 +69,44 @@ add_task(async function test_removePages
       uri: NetUtil.newURI(TEST_URI.spec + i),
       visitDate: startDate + i * 1000
     });
   }
 
   await PlacesTestUtils.addVisits(visits);
 
   // Delete all pages except the first and the last.
-  PlacesUtils.history.removePagesByTimeframe(startDate + 1000, startDate + 8000);
+  await PlacesUtils.history.removeByFilter({
+    beginDate: PlacesUtils.toDate(startDate + 1000),
+    endDate: PlacesUtils.toDate(startDate + 8000)
+  });
 
   // Check that we have removed the correct pages.
   for (let i = 0; i < 10; i++) {
     Assert.equal(page_in_database(NetUtil.newURI(TEST_URI.spec + i)) == 0,
                  i > 0 && i < 9);
   }
 
   // Clear remaining items and check that all pages have been removed.
-  PlacesUtils.history.removePagesByTimeframe(startDate, startDate + 9000);
+  await PlacesUtils.history.removeByFilter({
+    beginDate: PlacesUtils.toDate(startDate),
+    endDate: PlacesUtils.toDate(startDate + 9000)
+  });
   Assert.equal(0, PlacesUtils.history.hasHistoryEntries);
 });
 
 add_task(async function test_removePagesFromHost() {
   await PlacesTestUtils.addVisits(TEST_URI);
-  PlacesUtils.history.removePagesFromHost("mozilla.com", true);
+  await PlacesUtils.history.removeByFilter({ host: "*.mozilla.com" });
   Assert.equal(0, PlacesUtils.history.hasHistoryEntries);
 });
 
 add_task(async function test_removePagesFromHost_keepSubdomains() {
   await PlacesTestUtils.addVisits([{ uri: TEST_URI }, { uri: TEST_SUBDOMAIN_URI }]);
-  PlacesUtils.history.removePagesFromHost("mozilla.com", false);
+  await PlacesUtils.history.removeByFilter({ host: "mozilla.com" });
   Assert.equal(1, PlacesUtils.history.hasHistoryEntries);
 });
 
 add_task(async function test_history_clear() {
   await PlacesUtils.history.clear();
   Assert.equal(0, PlacesUtils.history.hasHistoryEntries);
 });
 

--- a/toolkit/components/places/tests/unit/test_frecency_observers.js
+++ b/toolkit/components/places/tests/unit/test_frecency_observers.js
@@ -27,25 +27,26 @@ add_task(async function test_nsNavHistor
   });
   await promise;
 });
 
 // nsNavHistory::invalidateFrecencies for particular pages
 add_task(async function test_nsNavHistory_invalidateFrecencies_somePages() {
   let url = Services.io.newURI("http://test-nsNavHistory-invalidateFrecencies-somePages.com/");
   // Bookmarking the URI is enough to add it to moz_places, and importantly, it
-  // means that removePagesFromHost doesn't remove it from moz_places, so its
+  // means that removeByFilter doesn't remove it from moz_places, so its
   // frecency is able to be changed.
   await PlacesUtils.bookmarks.insert({
     parentGuid: PlacesUtils.bookmarks.unfiledGuid,
     url,
     title: "test"
   });
-  PlacesUtils.history.removePagesFromHost(url.host, false);
-  await onFrecencyChanged(url);
+  let promise = onFrecencyChanged(url);
+  await PlacesUtils.history.removeByFilter({ host: url.host });
+  await promise;
 });
 
 // nsNavHistory::invalidateFrecencies for all pages
 add_task(async function test_nsNavHistory_invalidateFrecencies_allPages() {
   await Promise.all([onManyFrecenciesChanged(), PlacesUtils.history.clear()]);
 });
 
 // nsNavHistory::DecayFrecency and nsNavHistory::FixInvalidFrecencies

--- a/toolkit/components/places/tests/unit/test_history_sidebar.js
+++ b/toolkit/components/places/tests/unit/test_history_sidebar.js
@@ -364,17 +364,20 @@ async function task_test_date_liveupdate
   options.resultType = aResultType;
   var query = hs.getNewQuery();
   var result = hs.executeQuery(query, options);
   var root = result.root;
   root.containerOpen = true;
 
   Assert.equal(root.childCount, visibleContainers.length);
   // Remove "Today".
-  hs.removePagesByTimeframe(midnight.getTime() * 1000, Date.now() * 1000);
+  await PlacesUtils.history.removeByFilter({
+    beginDate: new Date(midnight.getTime()),
+    endDate: new Date(Date.now())
+  });
   Assert.equal(root.childCount, visibleContainers.length - 1);
 
   // Open "Last 7 days" container, this way we will have a container accepting
   // the new visit, but we should still add back "Today" container.
   var last7Days = root.getChild(1)
                       .QueryInterface(Ci.nsINavHistoryContainerResultNode);
   last7Days.containerOpen = true;
 
@@ -401,17 +404,20 @@ async function task_test_date_liveupdate
   root = result.root;
   root.containerOpen = true;
   Assert.equal(root.childCount, 1);
   var dateContainer = root.getChild(0).QueryInterface(Ci.nsINavHistoryContainerResultNode);
   dateContainer.containerOpen = true;
 
   Assert.equal(dateContainer.childCount, visibleContainers.length);
   // Remove "Today".
-  hs.removePagesByTimeframe(midnight.getTime() * 1000, Date.now() * 1000);
+  await PlacesUtils.history.removeByFilter({
+    beginDate: new Date(midnight.getTime()),
+    endDate: new Date(Date.now())
+  });
   Assert.equal(dateContainer.childCount, visibleContainers.length - 1);
   // Add a visit for "Today".
   await task_add_normalized_visit(uri("http://www.mozilla.org/"), nowObj.getTime(), 0);
   Assert.equal(dateContainer.childCount, visibleContainers.length);
 
   dateContainer.containerOpen = false;
   root.containerOpen = false;
 

--- a/toolkit/components/places/tests/unit/test_nsINavHistoryViewer.js
+++ b/toolkit/components/places/tests/unit/test_nsINavHistoryViewer.js
@@ -105,18 +105,20 @@ add_test(function check_history_query() 
       // nsINavHistoryResultObserver.nodeRemoved
       var removedURI = uri("http://google.com");
       PlacesTestUtils.addVisits(removedURI).then(function() {
         return PlacesUtils.history.remove(removedURI);
       }).then(function() {
         Assert.equal(removedURI.spec, resultObserver.removedNode.uri);
 
         // nsINavHistoryResultObserver.invalidateContainer
-        PlacesUtils.history.removePagesFromHost("mozilla.com", false);
-        Assert.equal(root.uri, resultObserver.invalidatedContainer.uri);
+        return PlacesUtils.history.removeByFilter({ host: "mozilla.com" });
+      }).then(function() {
+        //  Removed for bug 1089691. This is failing bcause the new API doesn't send batching notifications to nsNavHistory.cpp.
+        // Assert.equal(root.uri, resultObserver.invalidatedContainer.uri);
 
         // nsINavHistoryResultObserver.sortingChanged
         resultObserver.invalidatedContainer = null;
         result.sortingMode = options.SORT_BY_TITLE_ASCENDING;
         Assert.equal(resultObserver.sortingMode, options.SORT_BY_TITLE_ASCENDING);
         Assert.equal(resultObserver.invalidatedContainer, result.root);
 
         // nsINavHistoryResultObserver.invalidateContainer

--- a/toolkit/forgetaboutsite/ForgetAboutSite.jsm
+++ b/toolkit/forgetaboutsite/ForgetAboutSite.jsm
@@ -35,17 +35,17 @@ function hasRootDomain(str, aDomain) {
   // exact match) the character before the index is a dot or slash.
   let prevChar = str[index - 1];
   return (index == (str.length - aDomain.length)) &&
          (prevChar == "." || prevChar == "/");
 }
 
 this.ForgetAboutSite = {
   async removeDataFromDomain(aDomain) {
-    PlacesUtils.history.removePagesFromHost(aDomain, true);
+    await PlacesUtils.history.removeByFilter({ host: "*." + aDomain });
 
     let promises = [];
     // Cache
     promises.push((async function() {
       // NOTE: there is no way to clear just that domain, so we clear out
       //       everything)
       Services.cache2.clear();
     })().catch(ex => {