--- a/toolkit/components/places/PlacesRemoteTabsAutocompleteProvider.jsm
+++ b/toolkit/components/places/PlacesRemoteTabsAutocompleteProvider.jsm
@@ -8,74 +8,63 @@
  */
 
 "use strict";
 
 var EXPORTED_SYMBOLS = ["PlacesRemoteTabsAutocompleteProvider"];
 
 ChromeUtils.import("resource://gre/modules/XPCOMUtils.jsm");
 ChromeUtils.import("resource://gre/modules/Services.jsm");
+ChromeUtils.defineModuleGetter(this, "SyncedTabs",
+  "resource://services-sync/SyncedTabs.jsm");
 
 XPCOMUtils.defineLazyGetter(this, "weaveXPCService", function() {
   try {
     return Cc["@mozilla.org/weave/service;1"]
              .getService(Ci.nsISupports)
              .wrappedJSObject;
   } catch (ex) {
     // The app didn't build Sync.
   }
   return null;
 });
 
-XPCOMUtils.defineLazyGetter(this, "Weave", () => {
-  try {
-    let {Weave} = ChromeUtils.import("resource://services-sync/main.js", {});
-    return Weave;
-  } catch (ex) {
-    // The app didn't build Sync.
-  }
-  return null;
-});
-
 // from MDN...
 function escapeRegExp(string) {
   return string.replace(/[.*+?^${}()|[\]\\]/g, "\\$&");
 }
 
 // Build the in-memory structure we use.
-function buildItems() {
-  let clients = new Map(); // keyed by client guid, value is client
-  let tabs = new Map(); // keyed by string URL, value is {clientId, tab}
-
+async function buildItems() {
+  // This is sorted by most recent client, most recent tab.
+  let tabsData = [];
   // If Sync isn't initialized (either due to lag at startup or due to no user
   // being signed in), don't reach in to Weave.Service as that may initialize
   // Sync unnecessarily - we'll get an observer notification later when it
   // becomes ready and has synced a list of tabs.
   if (weaveXPCService.ready) {
-    let engine = Weave.Service.engineManager.get("tabs");
-
-    for (let [guid, client] of Object.entries(engine.getAllClients())) {
-      clients.set(guid, client);
+    let clients = await SyncedTabs.getTabClients();
+    SyncedTabs.sortTabClientsByLastUsed(clients);
+    for (let client of clients) {
       for (let tab of client.tabs) {
-        let url = tab.urlHistory[0];
-        tabs.set(url, { clientId: guid, tab });
+        tabsData.push({tab, client});
       }
     }
   }
-  return { clients, tabs };
+  return tabsData;
 }
 
 // Manage the cache of the items we use.
 // The cache itself.
 let _items = null;
 
 // Ensure the cache is good.
-function ensureItems() {
+async function ensureItems() {
   if (!_items) {
-    _items = buildItems();
+    _items = await buildItems();
   }
   return _items;
 }
 
 // A preference used to disable the showing of icons in remote tab records.
 const PREF_SHOW_REMOTE_ICONS = "services.sync.syncedTabs.showRemoteIcons";
 let showRemoteIcons;
 
@@ -112,35 +101,35 @@ Services.obs.addObserver(observe, "weave
 
 // Observe the pref for showing remote icons and prime our bool that reflects its value.
 Services.prefs.addObserver(PREF_SHOW_REMOTE_ICONS, observe);
 observe(null, "nsPref:changed", PREF_SHOW_REMOTE_ICONS);
 
 // This public object is a static singleton.
 var PlacesRemoteTabsAutocompleteProvider = {
   // a promise that resolves with an array of matching remote tabs.
-  getMatches(searchString) {
+  async getMatches(searchString) {
     // If Sync isn't configured we bail early.
     if (!weaveXPCService || !weaveXPCService.ready || !weaveXPCService.enabled) {
-      return Promise.resolve([]);
+      return [];
     }
 
     let re = new RegExp(escapeRegExp(searchString), "i");
     let matches = [];
-    let { tabs, clients } = ensureItems();
-    for (let [url, { clientId, tab }] of tabs) {
+    let tabsData = await ensureItems();
+    for (let {tab, client} of tabsData) {
+      let url = tab.url;
       let title = tab.title;
       if (url.match(re) || (title && title.match(re))) {
-        // lookup the client record.
-        let client = clients.get(clientId);
         let icon = showRemoteIcons ? tab.icon : null;
         // create the record we return for auto-complete.
         let record = {
           url, title, icon,
-          deviceClass: Weave.Service.clientsEngine.getClientType(clientId),
-          deviceName: client.clientName,
+          deviceName: client.name,
+          lastUsed: tab.lastUsed * 1000
         };
         matches.push(record);
       }
     }
-    return Promise.resolve(matches);
+
+    return matches;
   },
 };

--- a/toolkit/components/places/UnifiedComplete.js
+++ b/toolkit/components/places/UnifiedComplete.js
@@ -77,16 +77,20 @@ const FRECENCY_DEFAULT = 1000;
 // with the omnibox API. This is the maximum number of suggestions an extension
 // is allowed to add for a given search string.
 // This value includes the heuristic result.
 const MAXIMUM_ALLOWED_EXTENSION_MATCHES = 6;
 
 // After this time, we'll give up waiting for the extension to return matches.
 const MAXIMUM_ALLOWED_EXTENSION_TIME_MS = 3000;
 
+// By default we add remote tabs that have been used less than this time ago.
+// Any remaining remote tabs are added in queue if no other results are found.
+const RECENT_REMOTE_TAB_THRESHOLD_MS = 259200000; // 72 hours.
+
 // A regex that matches "single word" hostnames for whitelisting purposes.
 // The hostname will already have been checked for general validity, so we
 // don't need to be exhaustive here, so allow dashes anywhere.
 const REGEXP_SINGLEWORD_HOST = new RegExp("^[a-z0-9-]+$", "i");
 
 // Regex used to match userContextId.
 const REGEXP_USER_CONTEXT_ID = /(?:^| )user-context-id:(\d+)/;
 
@@ -931,16 +935,19 @@ function Search(searchString, searchPara
       this._previousSearchMatchTypes.push(MATCHTYPE.GENERAL);
     }
   }
 
   // Used to limit the number of adaptive results.
   this._adaptiveCount = 0;
   this._extraAdaptiveRows = [];
 
+  // Used to limit the number of remote tab results.
+  this._extraRemoteTabRows = [];
+
   // This is a replacement for this._result.matchCount, to be used when you need
   // to check how many "current" matches have been inserted.
   // Indeed this._result.matchCount may include matches from the previous search.
   this._currentMatchCount = 0;
 
   // These are used to avoid adding duplicate entries to the results.
   this._usedURLs = [];
   this._usedPlaceIds = new Set();
@@ -1218,16 +1225,22 @@ Search.prototype = {
     }
 
     // If we have some unused adaptive matches, add them now.
     while (this._extraAdaptiveRows.length &&
            this._currentMatchCount < Prefs.get("maxRichResults")) {
       this._addFilteredQueryMatch(this._extraAdaptiveRows.shift());
     }
 
+    // If we have some unused remote tab matches, add them now.
+    while (this._extraRemoteTabRows.length &&
+          this._currentMatchCount < Prefs.get("maxRichResults")) {
+      this._addMatch(this._extraRemoteTabRows.shift());
+    }
+
     // Ideally we should wait until MATCH_BOUNDARY_ANYWHERE, but that query
     // may be really slow and we may end up showing old results for too long.
     this._cleanUpNonCurrentMatches(MATCHTYPE.GENERAL);
 
     // If we do not have enough results, and our match type is
     // MATCH_BOUNDARY_ANYWHERE, search again with MATCH_ANYWHERE to get more
     // results.
     let count = this._counts[MATCHTYPE.GENERAL] + this._counts[MATCHTYPE.HEURISTIC];
@@ -1704,17 +1717,17 @@ Search.prototype = {
   },
 
   async _matchRemoteTabs() {
     // Bail out early for non-sync users.
     if (!syncUsernamePref) {
       return;
     }
     let matches = await PlacesRemoteTabsAutocompleteProvider.getMatches(this._originalSearchString);
-    for (let {url, title, icon, deviceName} of matches) {
+    for (let {url, title, icon, deviceName, lastUsed} of matches) {
       // It's rare that Sync supplies the icon for the page (but if it does, it
       // is a string URL)
       if (!icon) {
         icon = iconHelper(url);
       } else {
         icon = PlacesUtils.favicons
                           .getFaviconLinkForIcon(Services.io.newURI(icon)).spec;
       }
@@ -1725,17 +1738,21 @@ Search.prototype = {
         value: PlacesUtils.mozActionURI("remotetab", { url, deviceName }),
         comment: title || url,
         style: "action remotetab",
         // we want frecency > FRECENCY_DEFAULT so it doesn't get pushed out
         // by "remote" matches.
         frecency: FRECENCY_DEFAULT + 1,
         icon,
       };
-      this._addMatch(match);
+      if (lastUsed > (Date.now() - RECENT_REMOTE_TAB_THRESHOLD_MS)) {
+        this._addMatch(match);
+      } else {
+        this._extraRemoteTabRows.push(match);
+      }
     }
   },
 
   // TODO (bug 1054814): Use visited URLs to inform which scheme to use, if the
   // scheme isn't specificed.
   _matchUnknownUrl() {
     let flags = Ci.nsIURIFixup.FIXUP_FLAG_FIX_SCHEME_TYPOS |
                 Ci.nsIURIFixup.FIXUP_FLAG_ALLOW_KEYWORD_LOOKUP;

--- a/toolkit/components/places/tests/unifiedcomplete/test_remote_tab_matches.js
+++ b/toolkit/components/places/tests/unifiedcomplete/test_remote_tab_matches.js
@@ -23,16 +23,22 @@ MockTabsEngine.prototype = {
   },
 };
 
 // A clients engine that doesn't need to be a constructor.
 let MockClientsEngine = {
   getClientType(guid) {
     Assert.ok(guid.endsWith("desktop") || guid.endsWith("mobile"));
     return guid.endsWith("mobile") ? "phone" : "desktop";
+  },
+  remoteClientExists(id) {
+    return true;
+  },
+  getClientName(id) {
+    return id.endsWith("mobile") ? "My Phone" : "My Desktop";
   }
 };
 
 // Tell Sync about the mocks.
 Weave.Service.engineManager.register(MockTabsEngine);
 
 // Tell the Sync XPCOM service it is initialized.
 let weaveXPCService = Cc["@mozilla.org/weave/service;1"]
@@ -60,17 +66,17 @@ function makeRemoteTabMatch(url, deviceN
   };
 }
 
 // The tests.
 add_task(async function test_nomatch() {
   // Nothing matches.
   configureEngine({
     guid_desktop: {
-      clientName: "My Desktop",
+      id: "desktop",
       tabs: [{
         urlHistory: ["http://foo.com/"],
       }],
     }
   });
 
   // No remote tabs match here, so we only expect search results.
   await check_autocomplete({
@@ -79,17 +85,17 @@ add_task(async function test_nomatch() {
     matches: [ makeSearchMatch("ex", { heuristic: true }) ],
   });
 });
 
 add_task(async function test_minimal() {
   // The minimal client and tabs info we can get away with.
   configureEngine({
     guid_desktop: {
-      clientName: "My Desktop",
+      id: "desktop",
       tabs: [{
         urlHistory: ["http://example.com/"],
       }],
     }
   });
 
   await check_autocomplete({
     search: "ex",
@@ -98,17 +104,17 @@ add_task(async function test_minimal() {
                makeRemoteTabMatch("http://example.com/", "My Desktop") ],
   });
 });
 
 add_task(async function test_maximal() {
   // Every field that could possibly exist on a remote record.
   configureEngine({
     guid_mobile: {
-      clientName: "My Phone",
+      id: "mobile",
       tabs: [{
         urlHistory: ["http://example.com/"],
         title: "An Example",
         icon: "http://favicon",
       }],
     }
   });
 
@@ -123,17 +129,17 @@ add_task(async function test_maximal() {
              ],
   });
 });
 
 add_task(async function test_noShowIcons() {
   Services.prefs.setBoolPref("services.sync.syncedTabs.showRemoteIcons", false);
   configureEngine({
     guid_mobile: {
-      clientName: "My Phone",
+      id: "mobile",
       tabs: [{
         urlHistory: ["http://example.com/"],
         title: "An Example",
         icon: "http://favicon",
       }],
     }
   });
 
@@ -150,17 +156,17 @@ add_task(async function test_noShowIcons
   });
   Services.prefs.clearUserPref("services.sync.syncedTabs.showRemoteIcons");
 });
 
 add_task(async function test_matches_title() {
   // URL doesn't match search expression, should still match the title.
   configureEngine({
     guid_mobile: {
-      clientName: "My Phone",
+      id: "mobile",
       tabs: [{
         urlHistory: ["http://foo.com/"],
         title: "An Example",
       }],
     }
   });
 
   await check_autocomplete({
@@ -175,17 +181,17 @@ add_task(async function test_matches_tit
 
 add_task(async function test_localtab_matches_override() {
   // We have an open tab to the same page on a remote device, only "switch to
   // tab" should appear as duplicate detection removed the remote one.
 
   // First setup Sync to have the page as a remote tab.
   configureEngine({
     guid_mobile: {
-      clientName: "My Phone",
+      id: "mobile",
       tabs: [{
         urlHistory: ["http://foo.com/"],
         title: "An Example",
       }],
     }
   });
 
   // Setup Places to think the tab is open locally.
@@ -206,17 +212,17 @@ add_task(async function test_localtab_ma
 
 add_task(async function test_remotetab_matches_override() {
   // If We have an history result to the same page, we should only get the
   // remote tab match.
   let url = "http://foo.remote.com/";
   // First setup Sync to have the page as a remote tab.
   configureEngine({
     guid_mobile: {
-      clientName: "My Phone",
+      id: "mobile",
       tabs: [{
         urlHistory: [url],
         title: "An Example",
       }],
     }
   });
 
   // Setup Places to think the tab is open locally.
@@ -226,8 +232,52 @@ add_task(async function test_remotetab_m
     search: "rem",
     searchParam: "enable-actions",
     matches: [ makeSearchMatch("rem", { heuristic: true }),
                makeRemoteTabMatch("http://foo.remote.com/", "My Phone",
                                   { title: "An Example" }),
              ],
   });
 });
+
+add_task(async function test_many_remotetab_matches() {
+  await PlacesUtils.history.clear();
+
+  // In case we have many results, the most recent ones should be added on top,
+  // while others should be appended.
+  let url = "http://foo.remote.com/";
+  // First setup Sync to have the page as a remote tab.
+  configureEngine({
+    guid_mobile: {
+      id: "mobile",
+      tabs: Array(5).fill(0).map((e, i) => ({
+        urlHistory: [`${url}${i}`],
+        title: "A title",
+        lastUsed: (Date.now() / 1000) - (i * 86400) // i days ago.
+      })),
+    }
+  });
+
+  // Also add a local history result.
+  let historyUrl = url + "history/";
+  await PlacesTestUtils.addVisits(historyUrl);
+
+  await check_autocomplete({
+    search: "rem",
+    searchParam: "enable-actions",
+    checkSorting: true,
+    matches: [
+      makeSearchMatch("rem", { heuristic: true }),
+      makeRemoteTabMatch("http://foo.remote.com/0", "My Phone",
+                        { title: "A title" }),
+      makeRemoteTabMatch("http://foo.remote.com/1", "My Phone",
+                        { title: "A title" }),
+      makeRemoteTabMatch("http://foo.remote.com/2", "My Phone",
+                        { title: "A title" }),
+      { uri: Services.io.newURI(historyUrl),
+        title: "test visit for " + historyUrl },
+      makeRemoteTabMatch("http://foo.remote.com/3", "My Phone",
+                        { title: "A title" }),
+      makeRemoteTabMatch("http://foo.remote.com/4", "My Phone",
+                        { title: "A title" }),
+    ],
+  });
+});