--- a/browser/components/places/tests/browser/browser_library_batch_delete.js
+++ b/browser/components/places/tests/browser/browser_library_batch_delete.js
@@ -59,17 +59,17 @@ add_task(async function test_create_and_
      "Delete command is enabled");
   let promiseItemRemovedNotification = promiseBookmarksNotification(
     "onItemRemoved", (itemId, parentId, index, type, uri, guid) => guid == folderNode.bookmarkGuid);
   // Execute the delete command and check bookmark has been removed.
   PO._places.controller.doCommand("cmd_delete");
 
   await promiseItemRemovedNotification;
 
-  Assert.ok(!PlacesUtils.bookmarks.isBookmarked(testURI),
+  Assert.ok(!(await PlacesUtils.bookmarks.fetch({url: testURI})),
     "Bookmark has been correctly removed");
   // Test live update.
   Assert.equal(unsortedNode.childCount, 1, "Unsorted node has 1 child");
   Assert.equal(PO._places.selectedNode.title, "keepme", "Folder node selected");
   unsortedNode.containerOpen = false;
 });
 
 add_task(async function test_ensure_correct_selection_and_functionality() {

--- a/toolkit/components/places/nsINavBookmarksService.idl
+++ b/toolkit/components/places/nsINavBookmarksService.idl
@@ -8,17 +8,17 @@
 interface nsIFile;
 interface nsIURI;
 interface nsITransaction;
 interface nsINavHistoryBatchCallback;
 
 /**
  * Observer for bookmarks changes.
  */
-[scriptable, uuid(c06b4e7d-15b1-4d4f-bdf7-147d2be9084a)]
+[scriptable, uuid(4d00c221-2c4a-47ab-a617-abb324110492)]
 interface nsINavBookmarkObserver : nsISupports
 {
   /*
    * This observer should not be called for items that are tags.
    */
   readonly attribute boolean skipTags;
 
   /*
@@ -607,37 +607,16 @@ interface nsINavBookmarksService : nsISu
 
   /**
    * Get an item's type (bookmark, separator, folder).
    * The type is one of the TYPE_* constants defined above.
    */
   unsigned short getItemType(in long long aItemId);
 
   /**
-   * Returns true if the given URI is in any bookmark folder. If you want the
-   * results to be redirect-aware, use getBookmarkedURIFor()
-   */
-  boolean isBookmarked(in nsIURI aURI);
-
-  /**
-   * Used to see if the given URI is bookmarked, or any page that redirected to
-   * it is bookmarked. For example, if I bookmark "mozilla.org" by manually
-   * typing it in, and follow the bookmark, I will get redirected to
-   * "www.mozilla.org". Logically, this new page is also bookmarked. This
-   * function, if given "www.mozilla.org", will return the URI of the bookmark,
-   * in this case "mozilla.org".
-   *
-   * If there is no bookmarked page found, it will return NULL.
-   *
-   * @note The function will only return bookmarks in the first 2 levels of
-   *       redirection (1 -> 2 -> aURI).
-   */
-  nsIURI getBookmarkedURIFor(in nsIURI aURI);
-
-  /**
    * Change the bookmarked URI for a bookmark.
    * This changes which "place" the bookmark points at,
    * which means all annotations, etc are carried along.
    */
   void changeBookmarkURI(in long long aItemId,
                          in nsIURI aNewURI,
                          [optional] in unsigned short aSource);
 

--- a/toolkit/components/places/nsNavBookmarks.cpp
+++ b/toolkit/components/places/nsNavBookmarks.cpp
@@ -151,18 +151,17 @@ inline bool
 NeedsTombstone(const BookmarkData& aBookmark) {
   return aBookmark.syncStatus == nsINavBookmarksService::SYNC_STATUS_NORMAL;
 }
 
 } // namespace
 
 
 nsNavBookmarks::nsNavBookmarks()
-  : mItemCount(0)
-  , mRoot(0)
+  : mRoot(0)
   , mMenuRoot(0)
   , mTagsRoot(0)
   , mUnfiledRoot(0)
   , mToolbarRoot(0)
   , mMobileRoot(0)
   , mCanNotify(false)
   , mCacheObservers("bookmark-observers")
   , mBatching(false)
@@ -283,38 +282,16 @@ nsNavBookmarks::EnsureRoots()
 
   if (!mRoot || !mMenuRoot || !mToolbarRoot || !mTagsRoot || !mUnfiledRoot ||
       !mMobileRoot)
     return NS_ERROR_FAILURE;
 
   return NS_OK;
 }
 
-// nsNavBookmarks::IsBookmarkedInDatabase
-//
-//    This checks to see if the specified place_id is actually bookmarked.
-
-nsresult
-nsNavBookmarks::IsBookmarkedInDatabase(int64_t aPlaceId,
-                                       bool* aIsBookmarked)
-{
-  nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
-    "SELECT 1 FROM moz_bookmarks WHERE fk = :page_id"
-  );
-  NS_ENSURE_STATE(stmt);
-  mozStorageStatementScoper scoper(stmt);
-
-  nsresult rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("page_id"), aPlaceId);
-  NS_ENSURE_SUCCESS(rv, rv);
-  rv = stmt->ExecuteStep(aIsBookmarked);
-  NS_ENSURE_SUCCESS(rv, rv);
-  return NS_OK;
-}
-
-
 nsresult
 nsNavBookmarks::AdjustIndices(int64_t aFolderId,
                               int32_t aStartIndex,
                               int32_t aEndIndex,
                               int32_t aDelta)
 {
   NS_ASSERTION(aStartIndex >= 0 && aEndIndex <= INT32_MAX &&
                aStartIndex <= aEndIndex, "Bad indices");
@@ -2379,127 +2356,16 @@ nsNavBookmarks::FetchFolderInfo(int64_t 
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   return NS_OK;
 }
 
 
 NS_IMETHODIMP
-nsNavBookmarks::IsBookmarked(nsIURI* aURI, bool* aBookmarked)
-{
-  NS_ENSURE_ARG(aURI);
-  NS_ENSURE_ARG_POINTER(aBookmarked);
-
-  nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
-    "SELECT 1 FROM moz_bookmarks b "
-    "JOIN moz_places h ON b.fk = h.id "
-    "WHERE h.url_hash = hash(:page_url) AND h.url = :page_url"
-  );
-  NS_ENSURE_STATE(stmt);
-  mozStorageStatementScoper scoper(stmt);
-
-  nsresult rv = URIBinder::Bind(stmt, NS_LITERAL_CSTRING("page_url"), aURI);
-  NS_ENSURE_SUCCESS(rv, rv);
-  rv = stmt->ExecuteStep(aBookmarked);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  return NS_OK;
-}
-
-
-NS_IMETHODIMP
-nsNavBookmarks::GetBookmarkedURIFor(nsIURI* aURI, nsIURI** _retval)
-{
-  NS_ENSURE_ARG(aURI);
-  NS_ENSURE_ARG_POINTER(_retval);
-
-  *_retval = nullptr;
-
-  nsNavHistory* history = nsNavHistory::GetHistoryService();
-  NS_ENSURE_TRUE(history, NS_ERROR_OUT_OF_MEMORY);
-  int64_t placeId;
-  nsAutoCString placeGuid;
-  nsresult rv = history->GetIdForPage(aURI, &placeId, placeGuid);
-  NS_ENSURE_SUCCESS(rv, rv);
-  if (!placeId) {
-    // This URI is unknown, just return null.
-    return NS_OK;
-  }
-
-  // Check if a bookmark exists in the redirects chain for this URI.
-  // The query will also check if the page is directly bookmarked, and return
-  // the first found bookmark in case.  The check is directly on moz_bookmarks
-  // without special filtering.
-  // The next query finds the bookmarked ancestors in a redirects chain.
-  // It won't go further than 3 levels of redirects (a->b->c->your_place_id).
-  // To make this path 100% correct (up to any level) we would need either:
-  //  - A separate hash, build through recursive querying of the database.
-  //    This solution was previously implemented, but it had a negative effect
-  //    on startup since at each startup we have to recursively query the
-  //    database to rebuild a hash that is always the same across sessions.
-  //    It must be updated at each visit and bookmarks change too.  The code to
-  //    manage it is complex and prone to errors, sometimes causing incorrect
-  //    data fetches (for example wrong favicon for a redirected bookmark).
-  //  - A better way to track redirects for a visit.
-  //    We would need a separate table to track redirects, in the table we would
-  //    have visit_id, redirect_session.  To get all sources for
-  //    a visit then we could just join this table and get all visit_id that
-  //    are in the same redirect_session as our visit.  This has the drawback
-  //    that we can't ensure data integrity in the downgrade -> upgrade path,
-  //    since an old version would not update the table on new visits.
-  //
-  // For most cases these levels of redirects should be fine though, it's hard
-  // to hit a page that is 4 or 5 levels of redirects below a bookmarked page.
-  //
-  // As a bonus the query also checks first if place_id is already a bookmark,
-  // so you don't have to check that apart.
-
-  nsCString query = nsPrintfCString(
-    "SELECT url FROM moz_places WHERE id = ( "
-      "SELECT :page_id FROM moz_bookmarks WHERE fk = :page_id "
-      "UNION ALL "
-      "SELECT COALESCE(grandparent.place_id, parent.place_id) AS r_place_id "
-      "FROM moz_historyvisits dest "
-      "LEFT JOIN moz_historyvisits parent ON parent.id = dest.from_visit "
-                                        "AND dest.visit_type IN (%d, %d) "
-      "LEFT JOIN moz_historyvisits grandparent ON parent.from_visit = grandparent.id "
-                                             "AND parent.visit_type IN (%d, %d) "
-      "WHERE dest.place_id = :page_id "
-      "AND EXISTS(SELECT 1 FROM moz_bookmarks WHERE fk = r_place_id) "
-      "LIMIT 1 "
-    ")",
-    nsINavHistoryService::TRANSITION_REDIRECT_PERMANENT,
-    nsINavHistoryService::TRANSITION_REDIRECT_TEMPORARY,
-    nsINavHistoryService::TRANSITION_REDIRECT_PERMANENT,
-    nsINavHistoryService::TRANSITION_REDIRECT_TEMPORARY
-  );
-
-  nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(query);
-  NS_ENSURE_STATE(stmt);
-  mozStorageStatementScoper scoper(stmt);
-
-  rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("page_id"), placeId);
-  NS_ENSURE_SUCCESS(rv, rv);
-  bool hasBookmarkedOrigin;
-  if (NS_SUCCEEDED(stmt->ExecuteStep(&hasBookmarkedOrigin)) &&
-      hasBookmarkedOrigin) {
-    nsAutoCString spec;
-    rv = stmt->GetUTF8String(0, spec);
-    NS_ENSURE_SUCCESS(rv, rv);
-    rv = NS_NewURI(_retval, spec);
-    NS_ENSURE_SUCCESS(rv, rv);
-  }
-
-  // If there is no bookmarked origin, we will just return null.
-  return NS_OK;
-}
-
-
-NS_IMETHODIMP
 nsNavBookmarks::ChangeBookmarkURI(int64_t aBookmarkId, nsIURI* aNewURI,
                                   uint16_t aSource)
 {
   NS_ENSURE_ARG_MIN(aBookmarkId, 1);
   NS_ENSURE_ARG(aNewURI);
 
   BookmarkData bookmark;
   nsresult rv = FetchItemInfo(aBookmarkId, bookmark);

--- a/toolkit/components/places/nsNavBookmarks.h
+++ b/toolkit/components/places/nsNavBookmarks.h
@@ -309,18 +309,16 @@ private:
                                 const nsACString& aTitle,
                                 int64_t aSyncChangeDelta);
 
   /**
    * This is an handle to the Places database.
    */
   RefPtr<mozilla::places::Database> mDB;
 
-  int32_t mItemCount;
-
   nsMaybeWeakPtrArray<nsINavBookmarkObserver> mObservers;
 
   int64_t TagsRootId() {
     nsresult rv = EnsureRoots();
     NS_ENSURE_SUCCESS(rv, -1);
     return mTagsRoot;
   }
 
@@ -334,18 +332,16 @@ private:
   int64_t mMobileRoot;
 
   inline bool IsRoot(int64_t aFolderId) {
     return aFolderId == mRoot || aFolderId == mMenuRoot ||
            aFolderId == mTagsRoot || aFolderId == mUnfiledRoot ||
            aFolderId == mToolbarRoot || aFolderId == mMobileRoot;
   }
 
-  nsresult IsBookmarkedInDatabase(int64_t aBookmarkID, bool* aIsBookmarked);
-
   nsresult SetItemDateInternal(enum mozilla::places::BookmarkDate aDateType,
                                int64_t aSyncChangeDelta,
                                int64_t aItemId,
                                PRTime aValue);
 
   // Recursive method to build an array of folder's children
   nsresult GetDescendantChildren(int64_t aFolderId,
                                  const nsACString& aFolderGuid,
@@ -410,18 +406,16 @@ private:
    *        Array of bookmark ids.
    */
   nsresult GetBookmarkIdsForURITArray(nsIURI* aURI,
                                       nsTArray<int64_t>& aResult);
 
   nsresult GetBookmarksForURI(nsIURI* aURI,
                               nsTArray<BookmarkData>& _bookmarks);
 
-  int64_t RecursiveFindRedirectedBookmark(int64_t aPlaceId);
-
   class RemoveFolderTransaction final : public nsITransaction {
   public:
     RemoveFolderTransaction(int64_t aID, uint16_t aSource)
       : mID(aID)
       , mSource(aSource)
     {}
 
     NS_DECL_ISUPPORTS
@@ -476,19 +470,11 @@ private:
 
   // Used to enable and disable the observer notifications.
   bool mCanNotify;
   nsCategoryCache<nsINavBookmarkObserver> mCacheObservers;
 
   // Tracks whether we are in batch mode.
   // Note: this is only tracking bookmarks batches, not history ones.
   bool mBatching;
-
-  /**
-   * This function must be called every time a bookmark is removed.
-   *
-   * @param aURI
-   *        Uri to test.
-   */
-  nsresult UpdateKeywordsForRemovedBookmark(const BookmarkData& aBookmark);
 };
 
 #endif // nsNavBookmarks_h_

--- a/toolkit/components/places/tests/bookmarks/test_changeBookmarkURI.js
+++ b/toolkit/components/places/tests/bookmarks/test_changeBookmarkURI.js
@@ -14,54 +14,49 @@ var bmsvc = Cc["@mozilla.org/browser/nav
  *
  * @param aBookmarkId
  *        an item ID whose corresponding URI is aBookmarkedUri
  * @param aBookmarkedUri
  *        a bookmarked URI that has a corresponding item ID aBookmarkId
  * @param aUnbookmarkedUri
  *        a URI that is not currently bookmarked at all
  */
-function checkUris(aBookmarkId, aBookmarkedUri, aUnbookmarkedUri) {
+async function checkUris(aBookmarkId, aBookmarkedUri, aUnbookmarkedUri) {
   // Ensure that aBookmarkedUri equals some URI that is bookmarked
-  var uri = bmsvc.getBookmarkedURIFor(aBookmarkedUri);
-  do_check_neq(uri, null);
-  do_check_true(uri.equals(aBookmarkedUri));
+  let bm = await PlacesUtils.bookmarks.fetch({url: aBookmarkedUri});
 
-  // Ensure that aBookmarkedUri is considered bookmarked
-  do_check_true(bmsvc.isBookmarked(aBookmarkedUri));
+  do_check_neq(bm, null);
+  do_check_true(uri(bm.url).equals(aBookmarkedUri));
 
   // Ensure that the URI corresponding to aBookmarkId equals aBookmarkedUri
   do_check_true(bmsvc.getBookmarkURI(aBookmarkId).equals(aBookmarkedUri));
 
   // Ensure that aUnbookmarkedUri does not equal any URI that is bookmarked
-  uri = bmsvc.getBookmarkedURIFor(aUnbookmarkedUri);
-  do_check_eq(uri, null);
-
-  // Ensure that aUnbookmarkedUri is not considered bookmarked
-  do_check_false(bmsvc.isBookmarked(aUnbookmarkedUri));
+  bm = await PlacesUtils.bookmarks.fetch({url: aUnbookmarkedUri});
+  do_check_eq(bm, null);
 }
 
 // main
-function run_test() {
+add_task(async function() {
   // Create a folder
   var folderId = bmsvc.createFolder(bmsvc.toolbarFolder,
                                     "test",
                                     bmsvc.DEFAULT_INDEX);
 
   // Create 2 URIs
-  var uri1 = uri("http://www.dogs.com");
-  var uri2 = uri("http://www.cats.com");
+  var uri1 = uri("http://www.dogs.com/");
+  var uri2 = uri("http://www.cats.com/");
 
   // Bookmark the first one
   var bookmarkId = bmsvc.insertBookmark(folderId,
                                         uri1,
                                         bmsvc.DEFAULT_INDEX,
                                         "Dogs");
 
   // uri1 is bookmarked via bookmarkId, uri2 is not
-  checkUris(bookmarkId, uri1, uri2);
+  await checkUris(bookmarkId, uri1, uri2);
 
   // Change the URI of the bookmark to uri2
   bmsvc.changeBookmarkURI(bookmarkId, uri2);
 
   // uri2 is now bookmarked via bookmarkId, uri1 is not
-  checkUris(bookmarkId, uri2, uri1);
-}
+  await checkUris(bookmarkId, uri2, uri1);
+});

deleted file mode 100644
--- a/toolkit/components/places/tests/bookmarks/test_getBookmarkedURIFor.js
+++ /dev/null
@@ -1,79 +0,0 @@
-/* -*- 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/. */
-
- /**
-  * Test bookmarksService.getBookmarkedURIFor(aURI);
-  */
-
-var bs = PlacesUtils.bookmarks;
-
-add_task(async function test_getBookmarkedURIFor() {
-  let now = Date.now() * 1000;
-  const sourceURI = uri("http://test.mozilla.org/");
-  // Add a visit and a bookmark.
-  await PlacesTestUtils.addVisits({ uri: sourceURI, visitDate: now });
-  do_check_eq(bs.getBookmarkedURIFor(sourceURI), null);
-
-  let sourceItemId = bs.insertBookmark(bs.unfiledBookmarksFolder,
-                                       sourceURI,
-                                       bs.DEFAULT_INDEX,
-                                       "bookmark");
-  do_check_true(bs.getBookmarkedURIFor(sourceURI).equals(sourceURI));
-
-  // Add a redirected visit.
-  const permaURI = uri("http://perma.mozilla.org/");
-  await PlacesTestUtils.addVisits({
-    uri: permaURI,
-    transition: TRANSITION_REDIRECT_PERMANENT,
-    visitDate: now++,
-    referrer: sourceURI
-  });
-  do_check_true(bs.getBookmarkedURIFor(sourceURI).equals(sourceURI));
-  do_check_true(bs.getBookmarkedURIFor(permaURI).equals(sourceURI));
-  // Add a bookmark to the destination.
-  let permaItemId = bs.insertBookmark(bs.unfiledBookmarksFolder,
-                                      permaURI,
-                                      bs.DEFAULT_INDEX,
-                                      "bookmark");
-  do_check_true(bs.getBookmarkedURIFor(sourceURI).equals(sourceURI));
-  do_check_true(bs.getBookmarkedURIFor(permaURI).equals(permaURI));
-  // Now remove the bookmark on the destination.
-  bs.removeItem(permaItemId);
-  // We should see the source as bookmark.
-  do_check_true(bs.getBookmarkedURIFor(permaURI).equals(sourceURI));
-
-  // Add another redirected visit.
-  const tempURI = uri("http://perma.mozilla.org/");
-  await PlacesTestUtils.addVisits({
-    uri: tempURI,
-    transition: TRANSITION_REDIRECT_TEMPORARY,
-    visitDate: now++,
-    referrer: permaURI
-  });
-
-  do_check_true(bs.getBookmarkedURIFor(sourceURI).equals(sourceURI));
-  do_check_true(bs.getBookmarkedURIFor(tempURI).equals(sourceURI));
-  // Add a bookmark to the destination.
-  let tempItemId = bs.insertBookmark(bs.unfiledBookmarksFolder,
-                                     tempURI,
-                                     bs.DEFAULT_INDEX,
-                                     "bookmark");
-  do_check_true(bs.getBookmarkedURIFor(sourceURI).equals(sourceURI));
-  do_check_true(bs.getBookmarkedURIFor(tempURI).equals(tempURI));
-
-  // Now remove the bookmark on the destination.
-  bs.removeItem(tempItemId);
-  // We should see the source as bookmark.
-  do_check_true(bs.getBookmarkedURIFor(tempURI).equals(sourceURI));
-  // Remove the source bookmark as well.
-  bs.removeItem(sourceItemId);
-  do_check_eq(bs.getBookmarkedURIFor(tempURI), null);
-
-  // Try to pass in a never seen URI, should return null and a new entry should
-  // not be added to the database.
-  do_check_eq(bs.getBookmarkedURIFor(uri("http://does.not.exist/")), null);
-  do_check_false(page_in_database("http://does.not.exist/"));
-});

--- a/toolkit/components/places/tests/bookmarks/test_removeItem.js
+++ b/toolkit/components/places/tests/bookmarks/test_removeItem.js
@@ -1,27 +1,28 @@
 /* -*- 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/. */
 
 const DEFAULT_INDEX = PlacesUtils.bookmarks.DEFAULT_INDEX;
 
-function run_test() {
+add_task(async function test_removeItem() {
   // folder to hold this test
   var folderId =
     PlacesUtils.bookmarks.createFolder(PlacesUtils.toolbarFolderId,
                                        "", DEFAULT_INDEX);
 
   // add a bookmark to the new folder
   var bookmarkURI = uri("http://iasdjkf");
-  do_check_false(PlacesUtils.bookmarks.isBookmarked(bookmarkURI));
+  do_check_false(await PlacesUtils.bookmarks.fetch({url: bookmarkURI}));
   var bookmarkId = PlacesUtils.bookmarks.insertBookmark(folderId, bookmarkURI,
                                                         DEFAULT_INDEX, "");
   do_check_eq(PlacesUtils.bookmarks.getItemTitle(bookmarkId), "");
+  do_check_true(await PlacesUtils.bookmarks.fetch({url: bookmarkURI}));
 
   // remove the folder using removeItem
   PlacesUtils.bookmarks.removeItem(folderId);
   do_check_eq(PlacesUtils.bookmarks.getBookmarkIdsForURI(bookmarkURI).length, 0);
-  do_check_false(PlacesUtils.bookmarks.isBookmarked(bookmarkURI));
+  do_check_false(await PlacesUtils.bookmarks.fetch({url: bookmarkURI}));
   do_check_eq(PlacesUtils.bookmarks.getItemIndex(bookmarkId), -1);
-}
+});

--- a/toolkit/components/places/tests/bookmarks/xpcshell.ini
+++ b/toolkit/components/places/tests/bookmarks/xpcshell.ini
@@ -33,17 +33,16 @@ skip-if = toolkit == 'android'
 [test_bookmarks_insert.js]
 [test_bookmarks_insertTree.js]
 [test_bookmarks_notifications.js]
 [test_bookmarks_remove.js]
 [test_bookmarks_reorder.js]
 [test_bookmarks_search.js]
 [test_bookmarks_update.js]
 [test_changeBookmarkURI.js]
-[test_getBookmarkedURIFor.js]
 [test_keywords.js]
 [test_nsINavBookmarkObserver.js]
 [test_protectRoots.js]
 [test_removeFolderTransaction_reinsert.js]
 [test_removeItem.js]
 [test_savedsearches.js]
 [test_sync_fields.js]
 [test_untitled.js]

--- a/toolkit/components/places/tests/history/test_removeVisits.js
+++ b/toolkit/components/places/tests/history/test_removeVisits.js
@@ -274,18 +274,18 @@ add_task(async function remove_all_visit
   let root = PlacesUtils.history.executeQuery(query, opts).root;
   root.containerOpen = true;
   do_check_eq(root.childCount, 0);
   root.containerOpen = false;
 
   do_print("asyncHistory.isURIVisited should return false.");
   do_check_false(await promiseIsURIVisited(TEST_URI));
 
-  do_print("nsINavBookmarksService.isBookmarked should return true.");
-  do_check_true(PlacesUtils.bookmarks.isBookmarked(TEST_URI));
+  do_print("URI should be bookmarked");
+  do_check_true(await PlacesUtils.bookmarks.fetch({url: TEST_URI}));
   await PlacesTestUtils.promiseAsyncUpdates();
 
   do_print("Frecency should be smaller.")
   do_check_true(frecencyForUrl(TEST_URI) < initialFrecency);
 
   await cleanup();
 });
 

--- a/toolkit/components/places/tests/unit/test_placesTxn.js
+++ b/toolkit/components/places/tests/unit/test_placesTxn.js
@@ -163,25 +163,25 @@ add_task(async function test_create_item
 
   let txn = new PlacesCreateBookmarkTransaction(testURI, root, bmStartIndex,
                                                 "Test creating an item");
 
   txnManager.doTransaction(txn);
   let id = bmsvc.getBookmarkIdsForURI(testURI)[0];
   do_check_eq(observer._itemAddedId, id);
   do_check_eq(observer._itemAddedIndex, bmStartIndex);
-  do_check_true(bmsvc.isBookmarked(testURI));
+  do_check_neq(await PlacesUtils.bookmarks.fetch({url: testURI}), null);
 
   txn.undoTransaction();
   do_check_eq(observer._itemRemovedId, id);
   do_check_eq(observer._itemRemovedIndex, bmStartIndex);
-  do_check_false(bmsvc.isBookmarked(testURI));
+  do_check_eq(await PlacesUtils.bookmarks.fetch({url: testURI}), null);
 
   txn.redoTransaction();
-  do_check_true(bmsvc.isBookmarked(testURI));
+  do_check_neq(await PlacesUtils.bookmarks.fetch({url: testURI}), null);
   let newId = bmsvc.getBookmarkIdsForURI(testURI)[0];
   do_check_eq(observer._itemAddedIndex, bmStartIndex);
   do_check_eq(observer._itemAddedParent, root);
   do_check_eq(observer._itemAddedId, newId);
 
   txn.undoTransaction();
   do_check_eq(observer._itemRemovedId, newId);
   do_check_eq(observer._itemRemovedFolder, root);
@@ -194,17 +194,17 @@ add_task(async function test_create_item
   let folderId = bmsvc.createFolder(root, TEST_FOLDERNAME, bmsvc.DEFAULT_INDEX);
 
   let txn = new PlacesCreateBookmarkTransaction(testURI, folderId, bmStartIndex,
                                                 "Test creating item");
   txnManager.doTransaction(txn);
   let bkmId = bmsvc.getBookmarkIdsForURI(testURI)[0];
   do_check_eq(observer._itemAddedId, bkmId);
   do_check_eq(observer._itemAddedIndex, bmStartIndex);
-  do_check_true(bmsvc.isBookmarked(testURI));
+  do_check_neq(await PlacesUtils.bookmarks.fetch({url: testURI}), null);
 
   txn.undoTransaction();
   do_check_eq(observer._itemRemovedId, bkmId);
   do_check_eq(observer._itemRemovedIndex, bmStartIndex);
 
   txn.redoTransaction();
   let newBkmId = bmsvc.getBookmarkIdsForURI(testURI)[0];
   do_check_eq(observer._itemAddedIndex, bmStartIndex);
@@ -884,17 +884,17 @@ add_task(async function test_create_item
     do_check_eq(observer._itemChanged_isAnnotationProperty, true);
     do_check_true(annosvc.itemHasAnnotation(itemId, itemChildAnnoObj.name))
     do_check_eq(annosvc.getItemAnnotation(itemId, itemChildAnnoObj.name), itemChildAnnoObj.value);
 
     itemWChildTxn.undoTransaction();
     do_check_eq(observer._itemRemovedId, itemId);
 
     itemWChildTxn.redoTransaction();
-    do_check_true(bmsvc.isBookmarked(testURI));
+    do_check_neq(await PlacesUtils.bookmarks.fetch({url: testURI}), null);
     let newId = bmsvc.getBookmarkIdsForURI(testURI)[0];
     do_check_eq(newDateAdded, bmsvc.getItemDateAdded(newId));
     do_check_eq(observer._itemAddedId, newId);
     do_check_eq(observer._itemChangedProperty, "testAnno/testInt");
     do_check_eq(observer._itemChanged_isAnnotationProperty, true);
     do_check_true(annosvc.itemHasAnnotation(newId, itemChildAnnoObj.name))
     do_check_eq(annosvc.getItemAnnotation(newId, itemChildAnnoObj.name), itemChildAnnoObj.value);
 
@@ -911,25 +911,25 @@ add_task(async function test_create_fold
                                                          bmStartIndex, "childItem");
   let txn = new PlacesCreateFolderTransaction("Test creating a folder with child itemTxns",
                                               root, bmStartIndex, null, [childItemTxn]);
   try {
     txnManager.doTransaction(txn);
     let childItemId = bmsvc.getBookmarkIdsForURI(childURI)[0];
     do_check_eq(observer._itemAddedId, childItemId);
     do_check_eq(observer._itemAddedIndex, 0);
-    do_check_true(bmsvc.isBookmarked(childURI));
+    do_check_neq(await PlacesUtils.bookmarks.fetch({url: childURI}), null);
 
     txn.undoTransaction();
-    do_check_false(bmsvc.isBookmarked(childURI));
+    do_check_eq(await PlacesUtils.bookmarks.fetch({url: childURI}), null);
 
     txn.redoTransaction();
     let newchildItemId = bmsvc.getBookmarkIdsForURI(childURI)[0];
     do_check_eq(observer._itemAddedIndex, 0);
     do_check_eq(observer._itemAddedId, newchildItemId);
-    do_check_true(bmsvc.isBookmarked(childURI));
+    do_check_neq(await PlacesUtils.bookmarks.fetch({url: childURI}), null);
 
     txn.undoTransaction();
-    do_check_false(bmsvc.isBookmarked(childURI));
+    do_check_eq(await PlacesUtils.bookmarks.fetch({url: childURI}), null);
   } catch (ex) {
     do_throw("Setting a child item transaction in a createFolder transaction did throw: " + ex);
   }
 });