--- a/toolkit/components/places/tests/bookmarks/test_async_observers.js
+++ b/toolkit/components/places/tests/bookmarks/test_async_observers.js
@@ -103,17 +103,17 @@ add_task(function* test_add_icon() {
                                                  PlacesUtils.favicons.FAVICON_LOAD_NON_PRIVATE,
                                                  null,
                                                  Services.scriptSecurityManager.getSystemPrincipal());
   yield observerPromise;
 });
 
 add_task(function* test_remove_page() {
   let observerPromise = observer.setupCompletionPromise();
-  PlacesUtils.history.removePage(NetUtil.newURI("http://book.ma.rk/"));
+  yield PlacesUtils.history.remove("http://book.ma.rk/");
   yield observerPromise;
 });
 
 add_task(function cleanup() {
   PlacesUtils.bookmarks.removeObserver(observer, false);
 });
 
 add_task(function* shutdown() {

--- a/toolkit/components/places/tests/bookmarks/test_savedsearches.js
+++ b/toolkit/components/places/tests/bookmarks/test_savedsearches.js
@@ -166,17 +166,17 @@ add_task(function* test_savedsearches_hi
       // test live-update of query results - add a history visit that matches the query
       yield PlacesTestUtils.addVisits({
         uri: uri("http://foo.com"),
         title: searchTerm + "blah"
       });
       do_check_eq(node.childCount, 2);
 
       // test live-update of query results - delete a history visit that matches the query
-      PlacesUtils.history.removePage(uri("http://foo.com"));
+      yield PlacesUtils.history.remove("http://foo.com");
       do_check_eq(node.childCount, 1);
       node.containerOpen = false;
     }
 
     // test live-update of moved queries
     var tmpFolderId = PlacesUtils.bookmarks.createFolder(
       testRoot, "foo", PlacesUtils.bookmarks.DEFAULT_INDEX);
     PlacesUtils.bookmarks.moveItem(

--- a/toolkit/components/places/tests/queries/test_searchTerms_includeHidden.js
+++ b/toolkit/components/places/tests/queries/test_searchTerms_includeHidden.js
@@ -71,11 +71,11 @@ add_task(function* test_searchTerms_incl
     yield task_populateDB(HIDDEN_VISITS);
     let cc_update = root.childCount;
 
     root.containerOpen = false;
 
     do_check_eq(cc, data.expectedResults);
     do_check_eq(cc_update, data.expectedResults + (data.includeHidden ? 1 : 0));
 
-    PlacesUtils.bhistory.removePage(uri("http://hidden.example.com/"));
+    yield PlacesUtils.history.remove("http://hidden.example.com/");
   }
 });

--- a/toolkit/components/places/tests/unifiedcomplete/test_empty_search.js
+++ b/toolkit/components/places/tests/unifiedcomplete/test_empty_search.js
@@ -32,17 +32,17 @@ add_task(function* test_javascript_match
   yield addBookmark({ uri: uri5,
                       title: "title" });
   yield addBookmark({ uri: uri6,
                       title: "title" });
 
   addOpenPages(uri7, 1);
 
   // Now remove page 6 from history, so it is an unvisited bookmark.
-  PlacesUtils.history.removePage(uri6);
+  yield PlacesUtils.history.remove(uri6);
 
   do_print("Match everything");
   yield check_autocomplete({
     search: "foo",
     searchParam: "enable-actions",
     matches: [ makeSearchMatch("foo", { heuristic: true }),
                { uri: uri1, title: "title" },
                { uri: uri2, title: "title", style: ["bookmark"] },

--- a/toolkit/components/places/tests/unit/test_536081.js
+++ b/toolkit/components/places/tests/unit/test_536081.js
@@ -1,53 +1,34 @@
 /* -*- indent-tabs-mode: nil; js-indent-level: 2 -*- */
 /* vim:set ts=2 sw=2 sts=2 et: */
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
-var hs = Cc["@mozilla.org/browser/nav-history-service;1"].
-         getService(Ci.nsINavHistoryService);
-var bh = hs.QueryInterface(Ci.nsIBrowserHistory);
-var db = hs.QueryInterface(Ci.nsPIPlacesDatabase).DBConnection;
-
-const URLS = [
+const TEST_URL =
   { u: "http://www.google.com/search?q=testing%3Bthis&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:en-US:unofficial&client=firefox-a",
-    s: "goog" },
-];
-
-function run_test() {
-  run_next_test();
-}
+    s: "goog" };
 
-add_task(function* test_execute() {
-  for (let url of URLS) {
-    yield task_test_url(url);
-  }
-});
+add_task(function* () {
+  print("Testing url: " + TEST_URL.u);
+  yield PlacesTestUtils.addVisits(uri(TEST_URL.u));
 
-function* task_test_url(aURL) {
-  print("Testing url: " + aURL.u);
-  yield PlacesTestUtils.addVisits(uri(aURL.u));
-  let query = hs.getNewQuery();
-  query.searchTerms = aURL.s;
-  let options = hs.getNewQueryOptions();
-  let root = hs.executeQuery(query, options).root;
+  let query = PlacesUtils.history.getNewQuery();
+  query.searchTerms = TEST_URL.s;
+  let options = PlacesUtils.history.getNewQueryOptions();
+
+  let root = PlacesUtils.history.executeQuery(query, options).root;
   root.containerOpen = true;
   let cc = root.childCount;
   do_check_eq(cc, 1);
+
   print("Checking url is in the query.");
   let node = root.getChild(0);
   print("Found " + node.uri);
-  root.containerOpen = false;
-  bh.removePage(uri(node.uri));
-}
+
+  do_check_true(yield PlacesTestUtils.isPageInDB(TEST_URL.u));
 
-function check_empty_table(table_name) {
-  print("Checking url has been removed.");
-  let stmt = db.createStatement("SELECT count(*) FROM " + table_name);
-  try {
-    stmt.executeStep();
-    do_check_eq(stmt.getInt32(0), 0);
-  } finally {
-    stmt.finalize();
-  }
-}
+  root.containerOpen = false;
+  yield PlacesUtils.history.remove(node.uri);
+
+  do_check_false(yield PlacesTestUtils.isPageInDB(TEST_URL.u));
+});

--- a/toolkit/components/places/tests/unit/test_browserhistory.js
+++ b/toolkit/components/places/tests/unit/test_browserhistory.js
@@ -8,17 +8,17 @@ const TEST_URI = NetUtil.newURI("http://
 const TEST_SUBDOMAIN_URI = NetUtil.newURI("http://foobar.mozilla.com/");
 
 add_task(function* test_addPage() {
   yield PlacesTestUtils.addVisits(TEST_URI);
   do_check_eq(1, PlacesUtils.history.hasHistoryEntries);
 });
 
 add_task(function* test_removePage() {
-  PlacesUtils.bhistory.removePage(TEST_URI);
+  yield PlacesUtils.history.remove(TEST_URI);
   do_check_eq(0, PlacesUtils.history.hasHistoryEntries);
 });
 
 add_task(function* test_removePages() {
   let pages = [];
   for (let i = 0; i < 8; i++) {
     pages.push(NetUtil.newURI(TEST_URI.spec + i));
   }
@@ -35,17 +35,17 @@ add_task(function* test_removePages() {
   PlacesUtils.bookmarks.insertBookmark(PlacesUtils.unfiledBookmarksFolderId,
                                        pages[BOOKMARK_INDEX],
                                        PlacesUtils.bookmarks.DEFAULT_INDEX,
                                        "test bookmark");
   PlacesUtils.annotations.setPageAnnotation(pages[BOOKMARK_INDEX],
                                             ANNO_NAME, ANNO_VALUE, 0,
                                             Ci.nsIAnnotationService.EXPIRE_NEVER);
 
-  PlacesUtils.bhistory.removePages(pages, pages.length);
+  yield PlacesUtils.history.remove(pages);
   do_check_eq(0, PlacesUtils.history.hasHistoryEntries);
 
   // Check that the bookmark and its annotation still exist.
   do_check_true(PlacesUtils.bookmarks.getIdForItemAt(PlacesUtils.unfiledBookmarksFolderId, 0) > 0);
   do_check_eq(PlacesUtils.annotations.getPageAnnotation(pages[BOOKMARK_INDEX], ANNO_NAME),
               ANNO_VALUE);
 
   // Check the annotation on the non-bookmarked page does not exist anymore.

--- a/toolkit/components/places/tests/unit/test_history_observer.js
+++ b/toolkit/components/places/tests/unit/test_history_observer.js
@@ -146,17 +146,17 @@ add_task(function* test_onDeleteURI() {
   let promiseNotify = onNotify(function onDeleteURI(aURI, aGUID, aReason) {
     Assert.ok(aURI.equals(testuri));
     // Can't use do_check_guid_for_uri() here because the visit is already gone.
     Assert.equal(aGUID, testguid);
     Assert.equal(aReason, Ci.nsINavHistoryObserver.REASON_DELETED);
   });
   let [testuri] = yield task_add_visit();
   let testguid = do_get_guid_for_uri(testuri);
-  PlacesUtils.bhistory.removePage(testuri);
+  yield PlacesUtils.history.remove(testuri);
   yield promiseNotify;
 });
 
 add_task(function* test_onDeleteVisits() {
   let promiseNotify = onNotify(function onDeleteVisits(aURI, aVisitTime, aGUID,
                                                        aReason) {
     Assert.ok(aURI.equals(testuri));
     // Can't use do_check_guid_for_uri() here because the visit is already gone.
@@ -167,17 +167,17 @@ add_task(function* test_onDeleteVisits()
   let msecs24hrsAgo = Date.now() - (86400 * 1000);
   let [testuri] = yield task_add_visit(undefined, msecs24hrsAgo * 1000);
   // Add a bookmark so the page is not removed.
   PlacesUtils.bookmarks.insertBookmark(PlacesUtils.unfiledBookmarksFolderId,
                                        testuri,
                                        PlacesUtils.bookmarks.DEFAULT_INDEX,
                                        "test");
   let testguid = do_get_guid_for_uri(testuri);
-  PlacesUtils.bhistory.removePage(testuri);
+  yield PlacesUtils.history.remove(testuri);
   yield promiseNotify;
 });
 
 add_task(function* test_onTitleChanged() {
   let promiseNotify = onNotify(function onTitleChanged(aURI, aTitle, aGUID) {
     Assert.ok(aURI.equals(testuri));
     Assert.equal(aTitle, title);
     do_check_guid_for_uri(aURI, aGUID);

--- a/toolkit/components/places/tests/unit/test_hosts_triggers.js
+++ b/toolkit/components/places/tests/unit/test_hosts_triggers.js
@@ -78,21 +78,17 @@ add_task(function* test_moz_hosts_update
   yield PlacesTestUtils.addVisits(places);
 
   do_check_true(isHostInMozHosts(urls[0].uri, urls[0].typed, urls[0].prefix));
   do_check_true(isHostInMozHosts(urls[1].uri, urls[1].typed, urls[1].prefix));
   do_check_true(isHostInMozHosts(urls[2].uri, urls[2].typed, urls[2].prefix));
 });
 
 add_task(function* test_remove_places() {
-  for (let idx in urls) {
-    PlacesUtils.history.removePage(urls[idx].uri);
-  }
-
-  yield PlacesTestUtils.clearHistory();
+  yield PlacesUtils.history.remove(urls.map(x => x.uri));
 
   for (let idx in urls) {
     do_check_false(isHostInMozHosts(urls[idx].uri, urls[idx].typed, urls[idx].prefix));
   }
 });
 
 add_task(function* test_bookmark_changes() {
   let testUri = NetUtil.newURI("http://test.mozilla.org");
@@ -151,17 +147,17 @@ add_task(function* test_moz_hosts_www_re
                   , title: "test for " + aURIToKeep.spec
                   , transition: TRANSITION_TYPED
                   }];
 
     yield PlacesTestUtils.addVisits(places);
     print("removing " + aURIToRemove.spec + " keeping " + aURIToKeep);
     dump_table("moz_hosts");
     dump_table("moz_places");
-    PlacesUtils.history.removePage(aURIToRemove);
+    yield PlacesUtils.history.remove(aURIToRemove);
     let prefix = /www/.test(aURIToKeep.spec) ? "www." : null;
     dump_table("moz_hosts");
     dump_table("moz_places");
     do_check_true(isHostInMozHosts(aURIToKeep, true, prefix));
   }
 
   const TEST_URI = NetUtil.newURI("http://rem.mozilla.com");
   const TEST_WWW_URI = NetUtil.newURI("http://www.rem.mozilla.com");

--- a/toolkit/components/places/tests/unit/test_nsINavHistoryViewer.js
+++ b/toolkit/components/places/tests/unit/test_nsINavHistoryViewer.js
@@ -1,19 +1,14 @@
 /* -*- indent-tabs-mode: nil; js-indent-level: 2 -*- */
 /* vim:set ts=2 sw=2 sts=2 et: */
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
-// Get history service
-var histsvc = PlacesUtils.history;
-var bhist = PlacesUtils.bhistory;
-var bmsvc = PlacesUtils.bookmarks;
-
 var resultObserver = {
   insertedNode: null,
   nodeInserted(parent, node, newIndex) {
     this.insertedNode = node;
   },
   removedNode: null,
   nodeRemoved(parent, node, oldIndex) {
     this.removedNode = node;
@@ -82,21 +77,21 @@ var resultObserver = {
 
 var testURI = uri("http://mozilla.com");
 
 function run_test() {
   run_next_test();
 }
 
 add_test(function check_history_query() {
-  var options = histsvc.getNewQueryOptions();
+  var options = PlacesUtils.history.getNewQueryOptions();
   options.sortingMode = options.SORT_BY_DATE_DESCENDING;
   options.resultType = options.RESULTS_AS_VISIT;
-  var query = histsvc.getNewQuery();
-  var result = histsvc.executeQuery(query, options);
+  var query = PlacesUtils.history.getNewQuery();
+  var result = PlacesUtils.history.executeQuery(query, options);
   result.addObserver(resultObserver, false);
   var root = result.root;
   root.containerOpen = true;
 
   do_check_neq(resultObserver.openedContainer, null);
 
   // nsINavHistoryResultObserver.nodeInserted
   // add a visit
@@ -109,42 +104,43 @@ add_test(function check_history_query() 
 
     // nsINavHistoryResultObserver.itemTitleChanged for a leaf node
     PlacesTestUtils.addVisits({ uri: testURI, title: "baz" }).then(function() {
       do_check_eq(resultObserver.nodeChangedByTitle.title, "baz");
 
       // nsINavHistoryResultObserver.nodeRemoved
       var removedURI = uri("http://google.com");
       PlacesTestUtils.addVisits(removedURI).then(function() {
-        bhist.removePage(removedURI);
+        return PlacesUtils.history.remove(removedURI);
+      }).then(function() {
         do_check_eq(removedURI.spec, resultObserver.removedNode.uri);
 
         // nsINavHistoryResultObserver.invalidateContainer
-        bhist.removePagesFromHost("mozilla.com", false);
+        PlacesUtils.history.removePagesFromHost("mozilla.com", false);
         do_check_eq(root.uri, resultObserver.invalidatedContainer.uri);
 
         // nsINavHistoryResultObserver.sortingChanged
         resultObserver.invalidatedContainer = null;
         result.sortingMode = options.SORT_BY_TITLE_ASCENDING;
         do_check_eq(resultObserver.sortingMode, options.SORT_BY_TITLE_ASCENDING);
         do_check_eq(resultObserver.invalidatedContainer, result.root);
 
         // nsINavHistoryResultObserver.invalidateContainer
         PlacesTestUtils.clearHistoryEnabled().then(() => {
           do_check_eq(root.uri, resultObserver.invalidatedContainer.uri);
 
           // nsINavHistoryResultObserver.batching
           do_check_false(resultObserver.inBatchMode);
-          histsvc.runInBatchMode({
+          PlacesUtils.history.runInBatchMode({
             runBatched(aUserData) {
               do_check_true(resultObserver.inBatchMode);
             }
           }, null);
           do_check_false(resultObserver.inBatchMode);
-          bmsvc.runInBatchMode({
+          PlacesUtils.bookmarks.runInBatchMode({
             runBatched(aUserData) {
               do_check_true(resultObserver.inBatchMode);
             }
           }, null);
           do_check_false(resultObserver.inBatchMode);
 
           root.containerOpen = false;
           do_check_eq(resultObserver.closedContainer, resultObserver.openedContainer);
@@ -153,99 +149,107 @@ add_test(function check_history_query() 
           PlacesTestUtils.promiseAsyncUpdates().then(run_next_test);
         });
       });
     });
   });
 });
 
 add_test(function check_bookmarks_query() {
-  var options = histsvc.getNewQueryOptions();
-  var query = histsvc.getNewQuery();
-  query.setFolders([bmsvc.bookmarksMenuFolder], 1);
-  var result = histsvc.executeQuery(query, options);
+  var options = PlacesUtils.history.getNewQueryOptions();
+  var query = PlacesUtils.history.getNewQuery();
+  query.setFolders([PlacesUtils.bookmarks.bookmarksMenuFolder], 1);
+  var result = PlacesUtils.history.executeQuery(query, options);
   result.addObserver(resultObserver, false);
   var root = result.root;
   root.containerOpen = true;
 
   do_check_neq(resultObserver.openedContainer, null);
 
   // nsINavHistoryResultObserver.nodeInserted
   // add a bookmark
-  var testBookmark = bmsvc.insertBookmark(bmsvc.bookmarksMenuFolder, testURI, bmsvc.DEFAULT_INDEX, "foo");
+  var testBookmark =
+    PlacesUtils.bookmarks.insertBookmark(PlacesUtils.bookmarks.bookmarksMenuFolder,
+                                         testURI,
+                                         PlacesUtils.bookmarks.DEFAULT_INDEX,
+                                         "foo");
   do_check_eq("foo", resultObserver.insertedNode.title);
   do_check_eq(testURI.spec, resultObserver.insertedNode.uri);
 
   // nsINavHistoryResultObserver.nodeHistoryDetailsChanged
   // adding a visit causes nodeHistoryDetailsChanged for the folder
   do_check_eq(root.uri, resultObserver.nodeChangedByHistoryDetails.uri);
 
   // nsINavHistoryResultObserver.nodeTitleChanged for a leaf node
-  bmsvc.setItemTitle(testBookmark, "baz");
+  PlacesUtils.bookmarks.setItemTitle(testBookmark, "baz");
   do_check_eq(resultObserver.nodeChangedByTitle.title, "baz");
   do_check_eq(resultObserver.newTitle, "baz");
 
-  var testBookmark2 = bmsvc.insertBookmark(bmsvc.bookmarksMenuFolder, uri("http://google.com"), bmsvc.DEFAULT_INDEX, "foo");
-  bmsvc.moveItem(testBookmark2, bmsvc.bookmarksMenuFolder, 0);
+  var testBookmark2 =
+    PlacesUtils.bookmarks.insertBookmark(PlacesUtils.bookmarks.bookmarksMenuFolder,
+                                         uri("http://google.com"),
+                                         PlacesUtils.bookmarks.DEFAULT_INDEX,
+                                         "foo");
+  PlacesUtils.bookmarks.moveItem(testBookmark2, PlacesUtils.bookmarks.bookmarksMenuFolder, 0);
   do_check_eq(resultObserver.movedNode.itemId, testBookmark2);
 
   // nsINavHistoryResultObserver.nodeRemoved
-  bmsvc.removeItem(testBookmark2);
+  PlacesUtils.bookmarks.removeItem(testBookmark2);
   do_check_eq(testBookmark2, resultObserver.removedNode.itemId);
 
   // XXX nsINavHistoryResultObserver.invalidateContainer
 
   // nsINavHistoryResultObserver.sortingChanged
   resultObserver.invalidatedContainer = null;
   result.sortingMode = options.SORT_BY_TITLE_ASCENDING;
   do_check_eq(resultObserver.sortingMode, options.SORT_BY_TITLE_ASCENDING);
   do_check_eq(resultObserver.invalidatedContainer, result.root);
 
   // nsINavHistoryResultObserver.batching
   do_check_false(resultObserver.inBatchMode);
-  histsvc.runInBatchMode({
+  PlacesUtils.history.runInBatchMode({
     runBatched(aUserData) {
       do_check_true(resultObserver.inBatchMode);
     }
   }, null);
   do_check_false(resultObserver.inBatchMode);
-  bmsvc.runInBatchMode({
+  PlacesUtils.bookmarks.runInBatchMode({
     runBatched(aUserData) {
       do_check_true(resultObserver.inBatchMode);
     }
   }, null);
   do_check_false(resultObserver.inBatchMode);
 
   root.containerOpen = false;
   do_check_eq(resultObserver.closedContainer, resultObserver.openedContainer);
   result.removeObserver(resultObserver);
   resultObserver.reset();
   PlacesTestUtils.promiseAsyncUpdates().then(run_next_test);
 });
 
 add_test(function check_mixed_query() {
-  var options = histsvc.getNewQueryOptions();
-  var query = histsvc.getNewQuery();
+  var options = PlacesUtils.history.getNewQueryOptions();
+  var query = PlacesUtils.history.getNewQuery();
   query.onlyBookmarked = true;
-  var result = histsvc.executeQuery(query, options);
+  var result = PlacesUtils.history.executeQuery(query, options);
   result.addObserver(resultObserver, false);
   var root = result.root;
   root.containerOpen = true;
 
   do_check_neq(resultObserver.openedContainer, null);
 
   // nsINavHistoryResultObserver.batching
   do_check_false(resultObserver.inBatchMode);
-  histsvc.runInBatchMode({
+  PlacesUtils.history.runInBatchMode({
     runBatched(aUserData) {
       do_check_true(resultObserver.inBatchMode);
     }
   }, null);
   do_check_false(resultObserver.inBatchMode);
-  bmsvc.runInBatchMode({
+  PlacesUtils.bookmarks.runInBatchMode({
     runBatched(aUserData) {
       do_check_true(resultObserver.inBatchMode);
     }
   }, null);
   do_check_false(resultObserver.inBatchMode);
 
   root.containerOpen = false;
   do_check_eq(resultObserver.closedContainer, resultObserver.openedContainer);