--- a/toolkit/components/places/Database.cpp
+++ b/toolkit/components/places/Database.cpp
@@ -1235,17 +1235,22 @@ Database::InitSchema(bool* aDatabaseMigr
         NS_ENSURE_SUCCESS(rv, rv);
       }
 
       if (currentSchemaVersion < 45) {
         rv = MigrateV45Up();
         NS_ENSURE_SUCCESS(rv, rv);
       }
 
-      // Firefox 61 uses schema version 45.
+      if (currentSchemaVersion < 46) {
+        rv = MigrateV46Up();
+        NS_ENSURE_SUCCESS(rv, rv);
+      }
+
+      // Firefox 61 uses schema version 46.
 
       // Schema Upgrades must add migration code here.
       // >>> IMPORTANT! <<<
       // NEVER MIX UP SYNC AND ASYNC EXECUTION IN MIGRATORS, YOU MAY LOCK THE
       // CONNECTION AND CAUSE FURTHER STEPS TO FAIL.
       // In case, set a bool and do the async work in the ScopeExit guard just
       // before the migration steps.
     }
@@ -2078,29 +2083,67 @@ Database::MigrateV44Up() {
       "EXCEPT "
       "SELECT DISTINCT anno_attribute_id FROM moz_annos "
       "EXCEPT "
       "SELECT DISTINCT anno_attribute_id FROM moz_items_annos "
     ")"
   ));
   if (NS_FAILED(rv)) return rv;
 
-  return rv;
+  return NS_OK;
 }
 
 nsresult
 Database::MigrateV45Up() {
   nsCOMPtr<mozIStorageStatement> metaTableStmt;
   nsresult rv = mMainConn->CreateStatement(NS_LITERAL_CSTRING(
     "SELECT 1 FROM moz_meta"
   ), getter_AddRefs(metaTableStmt));
   if (NS_FAILED(rv)) {
     rv = mMainConn->ExecuteSimpleSQL(CREATE_MOZ_META);
     NS_ENSURE_SUCCESS(rv, rv);
   }
+  return NS_OK;
+}
+
+nsresult
+Database::MigrateV46Up() {
+  // Convert the existing queries. For simplicity we assume the user didn't
+  // edit these queries, and just do a 1:1 conversion.
+  nsresult rv = mMainConn->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
+    "UPDATE moz_places "
+       "SET url = 'place:tag=' || ( "
+          "SELECT title FROM moz_bookmarks "
+          "WHERE id = CAST(get_query_param(substr(url, 7), 'folder') AS INT) "
+       ") "
+    "WHERE url_hash BETWEEN hash('place', 'prefix_lo') AND "
+                           "hash('place', 'prefix_hi') "
+      "AND url LIKE '%type=7%' "
+  ));
+
+  // Recalculate hashes for all tag queries.
+  rv = mMainConn->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
+    "UPDATE moz_places SET url_hash = hash(url) "
+    "WHERE url_hash BETWEEN hash('place', 'prefix_lo') AND "
+                           "hash('place', 'prefix_hi') "
+      "AND url LIKE '%tag=%' "
+  ));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  // Update Sync fields for all tag queries.
+  rv = mMainConn->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
+    "UPDATE moz_bookmarks SET syncChangeCounter = syncChangeCounter + 1 "
+    "WHERE fk IN ( "
+      "SELECT id FROM moz_places "
+      "WHERE url_hash BETWEEN hash('place', 'prefix_lo') AND "
+                             "hash('place', 'prefix_hi') "
+        "AND url LIKE '%tag=%' "
+    ") "
+  ));
+  NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 nsresult
 Database::GetItemsWithAnno(const nsACString& aAnnoName, int32_t aItemType,
                            nsTArray<int64_t>& aItemIds)
 {

--- a/toolkit/components/places/Database.h
+++ b/toolkit/components/places/Database.h
@@ -14,17 +14,17 @@
 #include "mozilla/storage/StatementCache.h"
 #include "mozilla/Attributes.h"
 #include "nsIEventTarget.h"
 #include "Shutdown.h"
 #include "nsCategoryCache.h"
 
 // This is the schema version. Update it at any schema change and add a
 // corresponding migrateVxx method below.
-#define DATABASE_SCHEMA_VERSION 45
+#define DATABASE_SCHEMA_VERSION 46
 
 // Fired after Places inited.
 #define TOPIC_PLACES_INIT_COMPLETE "places-init-complete"
 // This topic is received when the profile is about to be lost.  Places does
 // initial shutdown work and notifies TOPIC_PLACES_SHUTDOWN to all listeners.
 // Any shutdown work that requires the Places APIs should happen here.
 #define TOPIC_PROFILE_CHANGE_TEARDOWN "profile-change-teardown"
 // Fired when Places is shutting down.  Any code should stop accessing Places
@@ -301,16 +301,17 @@ protected:
   nsresult MigrateV38Up();
   nsresult MigrateV39Up();
   nsresult MigrateV40Up();
   nsresult MigrateV41Up();
   nsresult MigrateV42Up();
   nsresult MigrateV43Up();
   nsresult MigrateV44Up();
   nsresult MigrateV45Up();
+  nsresult MigrateV46Up();
 
   nsresult UpdateBookmarkRootTitles();
 
   friend class ConnectionShutdownBlocker;
 
   int64_t CreateMobileRoot();
   nsresult GetItemsWithAnno(const nsACString& aAnnoName, int32_t aItemType,
                             nsTArray<int64_t>& aItemIds);

--- a/toolkit/components/places/tests/head_common.js
+++ b/toolkit/components/places/tests/head_common.js
@@ -1,14 +1,14 @@
 /* -*- indent-tabs-mode: nil; js-indent-level: 2 -*-
  * 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 CURRENT_SCHEMA_VERSION = 45;
+const CURRENT_SCHEMA_VERSION = 46;
 const FIRST_UPGRADABLE_SCHEMA_VERSION = 30;
 
 const NS_APP_USER_PROFILE_50_DIR = "ProfD";
 
 // Shortcuts to transitions type.
 const TRANSITION_LINK = Ci.nsINavHistoryService.TRANSITION_LINK;
 const TRANSITION_TYPED = Ci.nsINavHistoryService.TRANSITION_TYPED;
 const TRANSITION_BOOKMARK = Ci.nsINavHistoryService.TRANSITION_BOOKMARK;

new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/tests/migration/test_current_from_v45.js
@@ -0,0 +1,71 @@
+/* Any copyright is dedicated to the Public Domain.
+ * http://creativecommons.org/publicdomain/zero/1.0/ */
+
+"use strict";
+
+let gTags = [
+  { folder: 123456,
+    url: "place:folder=123456&type=7&queryType=1",
+    title: "tag1",
+    hash: "268505532566465",
+  },
+  { folder: 234567,
+    url: "place:folder=234567&type=7&queryType=1&somethingelse",
+    title: "tag2",
+    hash: "268506675127932",
+  },
+  { folder: 345678,
+    url: "place:type=7&folder=345678&queryType=1",
+    title: "tag3",
+    hash: " 268506471927988",
+  },
+];
+gTags.forEach(t => t.guid = t.title.padEnd(12, "_"));
+
+add_task(async function setup() {
+  await setupPlacesDatabase("places_v43.sqlite");
+
+  // Setup database contents to be migrated.
+  let path = OS.Path.join(OS.Constants.Path.profileDir, DB_FILENAME);
+  let db = await Sqlite.openConnection({ path });
+
+  for (let tag of gTags) {
+    // We can reuse the same guid, it doesn't matter for this test.
+    await db.execute(`INSERT INTO moz_places (url, guid, url_hash)
+                      VALUES (:url, :guid, :hash)
+                     `, { url: tag.url, guid: tag.guid, hash: tag.hash });
+    await db.execute(`INSERT INTO moz_bookmarks (id, fk, guid, title)
+                     VALUES (:id, (SELECT id FROM moz_places WHERE guid = :guid), :guid, :title)
+                    `, { id: tag.folder, guid: tag.guid, title: tag.title });
+  }
+
+  await db.close();
+});
+
+add_task(async function database_is_valid() {
+  // Accessing the database for the first time triggers migration.
+  Assert.equal(PlacesUtils.history.databaseStatus,
+               PlacesUtils.history.DATABASE_STATUS_UPGRADED);
+
+  let db = await PlacesUtils.promiseDBConnection();
+  Assert.equal((await db.getSchemaVersion()), CURRENT_SCHEMA_VERSION);
+});
+
+add_task(async function test_queries_converted() {
+  for (let tag of gTags) {
+    let bm = await PlacesUtils.bookmarks.fetch(tag.guid);
+    Assert.equal(bm.url.href, "place:tag=" + tag.title);
+  }
+});
+
+add_task(async function test_sync_fields() {
+  let db = await PlacesUtils.promiseDBConnection();
+  for (let tag of gTags) {
+    let rows = await db.execute(`
+      SELECT syncChangeCounter
+      FROM moz_bookmarks
+      WHERE guid = :guid
+    `, { guid: tag.guid });
+    Assert.equal(rows[0].getResultByIndex(0), 2);
+  }
+});

--- a/toolkit/components/places/tests/migration/xpcshell.ini
+++ b/toolkit/components/places/tests/migration/xpcshell.ini
@@ -18,8 +18,9 @@ support-files =
 [test_current_from_v34.js]
 [test_current_from_v34_no_roots.js]
 [test_current_from_v35.js]
 [test_current_from_v36.js]
 [test_current_from_v38.js]
 [test_current_from_v41.js]
 [test_current_from_v42.js]
 [test_current_from_v43.js]
+[test_current_from_v45.js]