--- a/browser/modules/DirectoryLinksProvider.jsm
+++ b/browser/modules/DirectoryLinksProvider.jsm
@@ -10,16 +10,17 @@ const Ci = Components.interfaces;
 const Cc = Components.classes;
 const Cu = Components.utils;
 const XMLHttpRequest =
   Components.Constructor("@mozilla.org/xmlextras/xmlhttprequest;1", "nsIXMLHttpRequest");
 
 Cu.import("resource://gre/modules/XPCOMUtils.jsm");
 Cu.import("resource://gre/modules/Services.jsm");
 Cu.import("resource://gre/modules/Task.jsm");
+Cu.import("resource://gre/modules/Timer.jsm");
 
 XPCOMUtils.defineLazyModuleGetter(this, "NetUtil",
   "resource://gre/modules/NetUtil.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "NewTabUtils",
   "resource://gre/modules/NewTabUtils.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "OS",
   "resource://gre/modules/osfile.jsm")
 XPCOMUtils.defineLazyModuleGetter(this, "Promise",
@@ -84,16 +85,21 @@ let DirectoryLinksProvider = {
    */
   _enhancedLinks: new Map(),
 
   /**
    * A mapping from site to a list of related link objects
    */
   _relatedLinks: new Map(),
 
+  /**
+   * A set of top sites that we can provide related links for
+   */
+  _topSitesWithRelatedLinks: new Set(),
+
   get _observedPrefs() Object.freeze({
     enhanced: PREF_NEWTAB_ENHANCED,
     linksURL: PREF_DIRECTORY_SOURCE,
     matchOSLocale: PREF_MATCH_OS_LOCALE,
     prefSelectedLocale: PREF_SELECTED_LOCALE,
   }),
 
   get _linksURL() {
@@ -427,37 +433,84 @@ let DirectoryLinksProvider = {
         }
         link.frecency = DIRECTORY_FRECENCY;
         links.push(link);
       });
       return links;
     }).catch(ex => {
       Cu.reportError(ex);
       return [];
-    }).then(aCallback);
+    }).then(links => {
+      aCallback(links);
+      this._populatePlacesLinks();
+    });
   },
 
   init: function DirectoryLinksProvider_init() {
     this._setDefaultEnhanced();
     this._addPrefsObserver();
     // setup directory file path and last download timestamp
     this._directoryFilePath = OS.Path.join(OS.Constants.Path.localProfileDir, DIRECTORY_LINKS_FILE);
     this._lastDownloadMS = 0;
+
+    NewTabUtils.placesProvider.addObserver(this);
+
     return Task.spawn(function() {
       // get the last modified time of the links file if it exists
       let doesFileExists = yield OS.File.exists(this._directoryFilePath);
       if (doesFileExists) {
         let fileInfo = yield OS.File.stat(this._directoryFilePath);
         this._lastDownloadMS = Date.parse(fileInfo.lastModificationDate);
       }
       // fetch directory on startup without force
       yield this._fetchAndCacheLinksIfNecessary();
     }.bind(this));
   },
 
+  _handleManyLinksChanged: function() {
+    this._topSitesWithRelatedLinks.clear();
+    this._relatedLinks.forEach((relatedLinks, site) => {
+      if (NewTabUtils.isTopPlacesSite(site)) {
+        this._topSitesWithRelatedLinks.add(site);
+      }
+    });
+  },
+
+  _handleLinkChanged: function(aLink) {
+    let changedLinkSite = NewTabUtils.extractSite(aLink.url);
+    if (!NewTabUtils.isTopPlacesSite(changedLinkSite)) {
+      this._topSitesWithRelatedLinks.delete(changedLinkSite);
+      return;
+    }
+
+    if (this._relatedLinks.has(changedLinkSite)) {
+      this._topSitesWithRelatedLinks.add(changedLinkSite);
+    }
+  },
+
+  _populatePlacesLinks: function () {
+    NewTabUtils.links.populateProviderCache(NewTabUtils.placesProvider, () => {
+      this._handleManyLinksChanged();
+    });
+  },
+
+  onLinkChanged: function (aProvider, aLink) {
+    // Make sure NewTabUtils.links handles the notification first.
+    setTimeout(() => {
+      this._handleLinkChanged(aLink);
+    }, 0);
+  },
+
+  onManyLinksChanged: function () {
+    // Make sure NewTabUtils.links handles the notification first.
+    setTimeout(() => {
+      this._handleManyLinksChanged();
+    }, 0);
+  },
+
   /**
    * Return the object to its pre-init state
    */
   reset: function DirectoryLinksProvider_reset() {
     delete this.__linksURL;
     this._removePrefsObserver();
     this._removeObservers();
   },

--- a/browser/modules/test/xpcshell/test_DirectoryLinksProvider.js
+++ b/browser/modules/test/xpcshell/test_DirectoryLinksProvider.js
@@ -14,16 +14,18 @@ Cu.import("resource://gre/modules/Promis
 Cu.import("resource://gre/modules/Http.jsm");
 Cu.import("resource://testing-common/httpd.js");
 Cu.import("resource://gre/modules/osfile.jsm");
 Cu.import("resource://gre/modules/Task.jsm");
 Cu.import("resource://gre/modules/XPCOMUtils.jsm");
 
 XPCOMUtils.defineLazyModuleGetter(this, "NetUtil",
   "resource://gre/modules/NetUtil.jsm");
+XPCOMUtils.defineLazyModuleGetter(this, "NewTabUtils",
+  "resource://gre/modules/NewTabUtils.jsm");
 
 do_get_profile();
 
 const DIRECTORY_LINKS_FILE = "directoryLinks.json";
 const DIRECTORY_FRECENCY = 1000;
 const kURLData = {"en-US": [{"url":"http://example.com","title":"LocalSource"}]};
 const kTestURL = 'data:application/json,' + JSON.stringify(kURLData);
 
@@ -53,16 +55,52 @@ Services.prefs.setBoolPref(kNewtabEnhanc
 const kHttpHandlerData = {};
 kHttpHandlerData[kExamplePath] = {"en-US": [{"url":"http://example.com","title":"RemoteSource"}]};
 
 const BinaryInputStream = CC("@mozilla.org/binaryinputstream;1",
                               "nsIBinaryInputStream",
                               "setInputStream");
 
 let gLastRequestPath;
+
+let relatedTile1 = {
+  url: "http://turbotax.com",
+  type: "related",
+  lastVisitDate: 4,
+  related: [
+    "taxact.com",
+    "hrblock.com",
+    "1040.com",
+    "taxslayer.com"
+  ]
+};
+let relatedTile2 = {
+  url: "http://irs.gov",
+  type: "related",
+  lastVisitDate: 3,
+  related: [
+    "taxact.com",
+    "hrblock.com",
+    "freetaxusa.com",
+    "taxslayer.com"
+  ]
+};
+let relatedTile3 = {
+  url: "http://hrblock.com",
+  type: "related",
+  lastVisitDate: 2,
+  related: [
+    "taxact.com",
+    "freetaxusa.com",
+    "1040.com",
+    "taxslayer.com"
+  ]
+};
+let someOtherSite = {url: "http://someothersite.com", title: "Not_A_Related_Site"};
+
 function getHttpHandler(path) {
   let code = 200;
   let body = JSON.stringify(kHttpHandlerData[path]);
   if (path == kFailPath) {
     code = 204;
   }
   return function(aRequest, aResponse) {
     gLastRequestPath = aRequest.path;
@@ -156,65 +194,32 @@ function promiseCleanDirectoryLinksProvi
 }
 
 function run_test() {
   // Set up a mock HTTP server to serve a directory page
   server = new HttpServer();
   server.registerPrefixHandler(kExamplePath, getHttpHandler(kExamplePath));
   server.registerPrefixHandler(kFailPath, getHttpHandler(kFailPath));
   server.start(kDefaultServerPort);
+  NewTabUtils.init();
 
   run_next_test();
 
   // Teardown.
   do_register_cleanup(function() {
     server.stop(function() { });
     DirectoryLinksProvider.reset();
     Services.prefs.clearUserPref(kLocalePref);
     Services.prefs.clearUserPref(kSourceUrlPref);
     Services.prefs.clearUserPref(kPingUrlPref);
     Services.prefs.clearUserPref(kNewtabEnhancedPref);
   });
 }
 
 add_task(function test_relatedLinksMap() {
-  let relatedTile1 = {
-    url: "http://turbotax.com",
-    type: "related",
-    lastVisitDate: 4,
-    related: [
-      "taxact.com",
-      "hrblock.com",
-      "1040.com",
-      "taxslayer.com"
-    ]
-  };
-  let relatedTile2 = {
-    url: "http://irs.gov",
-    type: "related",
-    lastVisitDate: 3,
-    related: [
-      "taxact.com",
-      "hrblock.com",
-      "freetaxusa.com",
-      "taxslayer.com"
-    ]
-  };
-  let relatedTile3 = {
-    url: "http://hrblock.com",
-    type: "related",
-    lastVisitDate: 2,
-    related: [
-      "taxact.com",
-      "freetaxusa.com",
-      "1040.com",
-      "taxslayer.com"
-    ]
-  };
-  let someOtherSite = {url: "http://someothersite.com", title: "Not_A_Related_Site"};
   let data = {"en-US": [relatedTile1, relatedTile2, relatedTile3, someOtherSite]};
   let dataURI = 'data:application/json,' + JSON.stringify(data);
 
   yield promiseSetupDirectoryLinksProvider({linksURL: dataURI});
   let links = yield fetchData();
 
   // Ensure the related tiles were not considered directory tiles.
   do_check_eq(links.length, 1);
@@ -235,16 +240,61 @@ add_task(function test_relatedLinksMap()
     for (let link of expected_data[site]) {
       isIdentical(relatedLinksItr.next().value, link);
     }
   })
 
   yield promiseCleanDirectoryLinksProvider();
 });
 
+add_task(function test_topSitesWithRelatedLinks() {
+  let topSites = ["site0.com", "1040.com", "site2.com", "hrblock.com", "site4.com", "freetaxusa.com", "site6.com"];
+  let origIsTopPlacesSite = NewTabUtils.isTopPlacesSite;
+  NewTabUtils.isTopPlacesSite = function(site) {
+    return topSites.indexOf(site) >= 0;
+  }
+
+  // We start off with no top sites with related links.
+  do_check_eq(DirectoryLinksProvider._topSitesWithRelatedLinks.size, 0);
+
+  let data = {"en-US": [relatedTile1, relatedTile2, relatedTile3, someOtherSite]};
+  let dataURI = 'data:application/json,' + JSON.stringify(data);
+
+  yield promiseSetupDirectoryLinksProvider({linksURL: dataURI});
+  let links = yield fetchData();
+
+  // Check we've populated related links as expected.
+  do_check_eq(DirectoryLinksProvider._relatedLinks.size, 5);
+
+  // When many sites change, we update _topSitesWithRelatedLinks as expected.
+  let expectedTopSitesWithRelatedLinks = ["hrblock.com", "1040.com", "freetaxusa.com"];
+  DirectoryLinksProvider._handleManyLinksChanged();
+  isIdentical([...DirectoryLinksProvider._topSitesWithRelatedLinks], expectedTopSitesWithRelatedLinks);
+
+  // Removing site6.com as a topsite has no impact on _topSitesWithRelatedLinks.
+  let popped = topSites.pop();
+  DirectoryLinksProvider._handleLinkChanged({url: "http://" + popped});
+  isIdentical([...DirectoryLinksProvider._topSitesWithRelatedLinks], expectedTopSitesWithRelatedLinks);
+
+  // Removing freetaxusa.com as a topsite will remove it from _topSitesWithRelatedLinks.
+  popped = topSites.pop();
+  expectedTopSitesWithRelatedLinks.pop();
+  DirectoryLinksProvider._handleLinkChanged({url: "http://" + popped});
+  isIdentical([...DirectoryLinksProvider._topSitesWithRelatedLinks], expectedTopSitesWithRelatedLinks);
+
+  // Re-adding freetaxusa.com as a topsite will add it to _topSitesWithRelatedLinks.
+  topSites.push(popped);
+  expectedTopSitesWithRelatedLinks.push(popped);
+  DirectoryLinksProvider._handleLinkChanged({url: "http://" + popped});
+  isIdentical([...DirectoryLinksProvider._topSitesWithRelatedLinks], expectedTopSitesWithRelatedLinks);
+
+  // Cleanup.
+  NewTabUtils.isTopPlacesSite = origIsTopPlacesSite;
+});
+
 add_task(function test_reportSitesAction() {
   yield DirectoryLinksProvider.init();
   let deferred, expectedPath, expectedPost;
   let done = false;
   server.registerPrefixHandler(kPingPath, (aRequest, aResponse) => {
     if (done) {
       return;
     }

--- a/toolkit/modules/NewTabUtils.jsm
+++ b/toolkit/modules/NewTabUtils.jsm
@@ -7,16 +7,17 @@
 this.EXPORTED_SYMBOLS = ["NewTabUtils"];
 
 const Ci = Components.interfaces;
 const Cc = Components.classes;
 const Cu = Components.utils;
 
 Cu.import("resource://gre/modules/Services.jsm");
 Cu.import("resource://gre/modules/XPCOMUtils.jsm");
+Cu.import("resource://gre/modules/Task.jsm");
 
 XPCOMUtils.defineLazyModuleGetter(this, "PlacesUtils",
   "resource://gre/modules/PlacesUtils.jsm");
 
 XPCOMUtils.defineLazyModuleGetter(this, "PageThumbs",
   "resource://gre/modules/PageThumbs.jsm");
 
 XPCOMUtils.defineLazyModuleGetter(this, "BinarySearch",
@@ -710,27 +711,22 @@ let PlacesProvider = {
  */
 let Links = {
   /**
    * The maximum number of links returned by getLinks.
    */
   maxNumLinks: LINKS_GET_LINKS_LIMIT,
 
   /**
-   * The link providers.
-   */
-  _providers: new Set(),
-
-  /**
    * A mapping from each provider to an object { sortedLinks, siteMap, linkMap }.
    * sortedLinks is the cached, sorted array of links for the provider.
    * siteMap is a mapping from base domains to URL count associated with the domain.
    * linkMap is a Map from link URLs to link objects.
    */
-  _providerLinks: new Map(),
+  _providers: new Map(),
 
   /**
    * The properties of link objects used to sort them.
    */
   _sortProperties: [
     "frecency",
     "lastVisitDate",
     "url",
@@ -741,28 +737,27 @@ let Links = {
    */
   _populateCallbacks: [],
 
   /**
    * Adds a link provider.
    * @param aProvider The link provider.
    */
   addProvider: function Links_addProvider(aProvider) {
-    this._providers.add(aProvider);
+    this._providers.set(aProvider, null);
     aProvider.addObserver(this);
   },
 
   /**
    * Removes a link provider.
    * @param aProvider The link provider.
    */
   removeProvider: function Links_removeProvider(aProvider) {
     if (!this._providers.delete(aProvider))
       throw new Error("Unknown provider");
-    this._providerLinks.delete(aProvider);
   },
 
   /**
    * Populates the cache with fresh links from the providers.
    * @param aCallback The callback to call when finished (optional).
    * @param aForce When true, populates the cache even when it's already filled.
    */
   populateCache: function Links_populateCache(aCallback, aForce) {
@@ -785,17 +780,17 @@ let Links = {
           } catch (e) {
             // We want to proceed even if a callback fails.
           }
         }
       }
     }
 
     let numProvidersRemaining = this._providers.size;
-    for (let provider of this._providers) {
+    for (let [provider, links] of this._providers) {
       this._populateProviderCache(provider, () => {
         if (--numProvidersRemaining == 0)
           executeCallbacks();
       }, aForce);
     }
 
     this._addObserver();
   },
@@ -835,17 +830,19 @@ let Links = {
 
     return pinnedLinks;
   },
 
   /**
    * Resets the links cache.
    */
   resetCache: function Links_resetCache() {
-    this._providerLinks.clear();
+    for (let provider of this._providers.keys()) {
+      this._providers.set(provider, null);
+    }
   },
 
   /**
    * Compares two links.
    * @param aLink1 The first link.
    * @param aLink2 The second link.
    * @return A negative number if aLink1 is ordered before aLink2, zero if
    *         aLink1 and aLink2 have the same ordering, or a positive number if
@@ -873,56 +870,80 @@ let Links = {
     let previousURLCount = map.get(site);
     if (previousURLCount === 1) {
       map.delete(site);
     } else {
       map.set(site, previousURLCount - 1);
     }
   },
 
+  populateProviderCache: function(provider, callback) {
+    if (!this._providers.has(provider)) {
+      throw new Error("Can only populate provider cache for existing provider.");
+    }
+
+    return this._populateProviderCache(provider, callback, false);
+  },
+
   /**
    * Calls getLinks on the given provider and populates our cache for it.
    * @param aProvider The provider whose cache will be populated.
    * @param aCallback The callback to call when finished.
    * @param aForce When true, populates the provider's cache even when it's
    *               already filled.
    */
-  _populateProviderCache: function Links_populateProviderCache(aProvider, aCallback, aForce) {
-    if (this._providerLinks.has(aProvider) && !aForce) {
-      aCallback();
-    } else {
-      aProvider.getLinks(links => {
-        // Filter out null and undefined links so we don't have to deal with
-        // them in getLinks when merging links from providers.
-        links = links.filter((link) => !!link);
-        this._providerLinks.set(aProvider, {
-          sortedLinks: links,
-          siteMap: links.reduce((map, link) => {
+  _populateProviderCache: function (aProvider, aCallback, aForce) {
+    let cache = this._providers.get(aProvider);
+    let createCache = !cache;
+    if (createCache) {
+      cache = {
+        // Start with a resolved promise.
+        populatePromise: new Promise(resolve => resolve()),
+      };
+      this._providers.set(aProvider, cache);
+    }
+    // Chain the populatePromise so that calls are effectively queued.
+    cache.populatePromise = cache.populatePromise.then(() => {
+      return new Promise(resolve => {
+        if (!createCache && !aForce) {
+          aCallback();
+          resolve();
+          return;
+        }
+        aProvider.getLinks(links => {
+          // Filter out null and undefined links so we don't have to deal with
+          // them in getLinks when merging links from providers.
+          links = links.filter((link) => !!link);
+          cache.sortedLinks = links;
+          cache.siteMap = links.reduce((map, link) => {
             this._incrementSiteMap(map, link);
             return map;
-          }, new Map()),
-          linkMap: links.reduce((map, link) => {
+          }, new Map());
+          cache.linkMap = links.reduce((map, link) => {
             map.set(link.url, link);
             return map;
-          }, new Map()),
+          }, new Map());
+          aCallback();
+          resolve();
         });
-        aCallback();
       });
-    }
+    });
   },
 
   /**
    * Merges the cached lists of links from all providers whose lists are cached.
    * @return The merged list.
    */
   _getMergedProviderLinks: function Links__getMergedProviderLinks() {
     // Build a list containing a copy of each provider's sortedLinks list.
     let linkLists = [];
-    for (let links of this._providerLinks.values()) {
-      linkLists.push(links.sortedLinks.slice());
+    for (let links of this._providers.values()) {
+      if (links) {
+        linkLists.push(links.sortedLinks.slice());
+      }
     }
 
     function getNextLink() {
       let minLinks = null;
       for (let links of linkLists) {
         if (links.length &&
             (!minLinks || Links.compareLinks(links[0], minLinks[0]) < 0))
           minLinks = links;
@@ -946,17 +967,17 @@ let Links = {
    * @param aLink The link that changed.  If the link is new, it must have all
    *              of the _sortProperties.  Otherwise, it may have as few or as
    *              many as is convenient.
    */
   onLinkChanged: function Links_onLinkChanged(aProvider, aLink) {
     if (!("url" in aLink))
       throw new Error("Changed links must have a url property");
 
-    let links = this._providerLinks.get(aProvider);
+    let links = this._providers.get(aProvider);
     if (!links)
       // This is not an error, it just means that between the time the provider
       // was added and the future time we call getLinks on it, it notified us of
       // a change.
       return;
 
     let { sortedLinks, siteMap, linkMap } = links;
     let existingLink = linkMap.get(aLink.url);
@@ -1205,17 +1226,17 @@ this.NewTabUtils = {
       ExpirationFilter.init();
       Telemetry.init();
       return true;
     }
     return false;
   },
 
   isTopSiteGivenProvider: function(aSite, aProvider) {
-    return Links._providerLinks.get(aProvider).siteMap.has(aSite);
+    return Links._providers.get(aProvider).siteMap.has(aSite);
   },
 
   isTopPlacesSite: function(aSite) {
     return this.isTopSiteGivenProvider(aSite, PlacesProvider);
   },
 
   /**
    * Restores all sites that have been removed from the grid.
@@ -1243,10 +1264,11 @@ this.NewTabUtils = {
     Links.populateCache(aCallback, true);
   },
 
   links: Links,
   allPages: AllPages,
   linkChecker: LinkChecker,
   pinnedLinks: PinnedLinks,
   blockedLinks: BlockedLinks,
-  gridPrefs: GridPrefs
+  gridPrefs: GridPrefs,
+  placesProvider: PlacesProvider
 };

--- a/toolkit/modules/tests/xpcshell/test_NewTabUtils.js
+++ b/toolkit/modules/tests/xpcshell/test_NewTabUtils.js
@@ -1,33 +1,58 @@
 /* Any copyright is dedicated to the Public Domain.
    http://creativecommons.org/publicdomain/zero/1.0/ */
 
 // See also browser/base/content/test/newtab/.
 
 const { classes: Cc, interfaces: Ci, results: Cr, utils: Cu } = Components;
 Cu.import("resource://gre/modules/NewTabUtils.jsm");
 Cu.import("resource://gre/modules/Promise.jsm");
+Cu.import("resource://gre/modules/Task.jsm");
 
 function run_test() {
   run_next_test();
 }
 
+add_task(function populatePromise() {
+  let count = 0;
+  let expectedLinks = makeLinks(0, 10, 2);
+
+  let getLinksFcn = Task.async(function* (callback) {
+    //Should not be calling getLinksFcn twice
+    count++;
+    do_check_eq(count, 1);
+    yield Promise.resolve();
+    callback(expectedLinks);
+  });
+
+  let provider = new TestProvider(getLinksFcn);
+
+  NewTabUtils.initWithoutProviders();
+  NewTabUtils.links.addProvider(provider);
+
+  NewTabUtils.links.populateProviderCache(provider, () => {});
+  NewTabUtils.links.populateProviderCache(provider, () => {
+    do_check_links(NewTabUtils.links.getLinks(), expectedLinks);
+    NewTabUtils.links.removeProvider(provider);
+  });
+});
+
 add_task(function isTopSiteGivenProvider() {
   let expectedLinks = makeLinks(0, 10, 2);
 
   // The lowest 2 frecencies have the same base domain.
   expectedLinks[expectedLinks.length - 2].url = expectedLinks[expectedLinks.length - 1].url + "Test";
 
   let provider = new TestProvider(done => done(expectedLinks));
   provider.maxNumLinks = expectedLinks.length;
 
   NewTabUtils.initWithoutProviders();
   NewTabUtils.links.addProvider(provider);
-  NewTabUtils.links.populateCache(function () {}, false);
+  yield new Promise(resolve => NewTabUtils.links.populateCache(resolve));
 
   do_check_eq(NewTabUtils.isTopSiteGivenProvider("example2.com", provider), true);
   do_check_eq(NewTabUtils.isTopSiteGivenProvider("example1.com", provider), false);
 
   // Push out frecency 2 because the maxNumLinks is reached when adding frecency 3
   let newLink = makeLink(3);
   provider.notifyLinkChanged(newLink);
 
@@ -57,18 +82,17 @@ add_task(function multipleProviders() {
   let evenProvider = new TestProvider(done => done(evenLinks));
   let oddLinks = makeLinks(0, 2 * NewTabUtils.links.maxNumLinks - 1, 2);
   let oddProvider = new TestProvider(done => done(oddLinks));
 
   NewTabUtils.initWithoutProviders();
   NewTabUtils.links.addProvider(evenProvider);
   NewTabUtils.links.addProvider(oddProvider);
 
-  // This is sync since the providers' getLinks are sync.
-  NewTabUtils.links.populateCache(function () {}, false);
+  yield new Promise(resolve => NewTabUtils.links.populateCache(resolve));
 
   let links = NewTabUtils.links.getLinks();
   let expectedLinks = makeLinks(NewTabUtils.links.maxNumLinks,
                                 2 * NewTabUtils.links.maxNumLinks,
                                 1);
   do_check_eq(links.length, NewTabUtils.links.maxNumLinks);
   do_check_links(links, expectedLinks);
 
@@ -78,18 +102,17 @@ add_task(function multipleProviders() {
 
 add_task(function changeLinks() {
   let expectedLinks = makeLinks(0, 20, 2);
   let provider = new TestProvider(done => done(expectedLinks));
 
   NewTabUtils.initWithoutProviders();
   NewTabUtils.links.addProvider(provider);
 
-  // This is sync since the provider's getLinks is sync.
-  NewTabUtils.links.populateCache(function () {}, false);
+  yield new Promise(resolve => NewTabUtils.links.populateCache(resolve));
 
   do_check_links(NewTabUtils.links.getLinks(), expectedLinks);
 
   // Notify of a new link.
   let newLink = makeLink(19);
   expectedLinks.splice(1, 0, newLink);
   provider.notifyLinkChanged(newLink);
   do_check_links(NewTabUtils.links.getLinks(), expectedLinks);
@@ -119,56 +142,58 @@ add_task(function changeLinks() {
   expectedLinks.pop();
   do_check_eq(expectedLinks.length, provider.maxNumLinks); // Sanity check.
   provider.notifyLinkChanged(newLink);
   do_check_links(NewTabUtils.links.getLinks(), expectedLinks);
 
   // Notify of many links changed.
   expectedLinks = makeLinks(0, 3, 1);
   provider.notifyManyLinksChanged();
-  // NewTabUtils.links will now repopulate its cache, which is sync since
-  // the provider's getLinks is sync.
+
+  // Since _populateProviderCache() is async, we must wait until the provider's
+  // populate promise has been resolved.
+  yield NewTabUtils.links._providers.get(provider).populatePromise;
+
+  // NewTabUtils.links will now repopulate its cache
   do_check_links(NewTabUtils.links.getLinks(), expectedLinks);
 
   NewTabUtils.links.removeProvider(provider);
 });
 
 add_task(function oneProviderAlreadyCached() {
   let links1 = makeLinks(0, 10, 1);
   let provider1 = new TestProvider(done => done(links1));
 
   NewTabUtils.initWithoutProviders();
   NewTabUtils.links.addProvider(provider1);
 
-  // This is sync since the provider's getLinks is sync.
-  NewTabUtils.links.populateCache(function () {}, false);
+  yield new Promise(resolve => NewTabUtils.links.populateCache(resolve));
   do_check_links(NewTabUtils.links.getLinks(), links1);
 
   let links2 = makeLinks(10, 20, 1);
   let provider2 = new TestProvider(done => done(links2));
   NewTabUtils.links.addProvider(provider2);
 
-  NewTabUtils.links.populateCache(function () {}, false);
+  yield new Promise(resolve => NewTabUtils.links.populateCache(resolve));
   do_check_links(NewTabUtils.links.getLinks(), links2.concat(links1));
 
   NewTabUtils.links.removeProvider(provider1);
   NewTabUtils.links.removeProvider(provider2);
 });
 
 add_task(function newLowRankedLink() {
   // Init a provider with 10 links and make its maximum number also 10.
   let links = makeLinks(0, 10, 1);
   let provider = new TestProvider(done => done(links));
   provider.maxNumLinks = links.length;
 
   NewTabUtils.initWithoutProviders();
   NewTabUtils.links.addProvider(provider);
 
-  // This is sync since the provider's getLinks is sync.
-  NewTabUtils.links.populateCache(function () {}, false);
+  yield new Promise(resolve => NewTabUtils.links.populateCache(resolve));
   do_check_links(NewTabUtils.links.getLinks(), links);
 
   // Notify of a new link that's low-ranked enough not to make the list.
   let newLink = makeLink(0);
   provider.notifyLinkChanged(newLink);
   do_check_links(NewTabUtils.links.getLinks(), links);
 
   // Notify about the new link's title change.