--- a/browser/components/newtab/NewTabMessages.jsm
+++ b/browser/components/newtab/NewTabMessages.jsm
@@ -1,71 +1,93 @@
 /*global
   NewTabWebChannel,
   NewTabPrefsProvider,
+  PlacesProvider,
   Preferences,
   XPCOMUtils
 */
 
 /* exported NewTabMessages */
 
 "use strict";
 
 const {utils: Cu} = Components;
 Cu.import("resource://gre/modules/Preferences.jsm");
 Cu.import("resource://gre/modules/XPCOMUtils.jsm");
 
+XPCOMUtils.defineLazyModuleGetter(this, "PlacesProvider",
+                                  "resource:///modules/PlacesProvider.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "PreviewProvider",
                                   "resource:///modules/PreviewProvider.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "NewTabPrefsProvider",
                                   "resource:///modules/NewTabPrefsProvider.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "NewTabWebChannel",
                                   "resource:///modules/NewTabWebChannel.jsm");
 
 this.EXPORTED_SYMBOLS = ["NewTabMessages"];
 
 const PREF_ENABLED = "browser.newtabpage.remote";
 
 // Action names are from the content's perspective. in from chrome == out from content
 // Maybe replace the ACTION objects by a bi-directional Map a bit later?
 const ACTIONS = {
+  inboundActions: [
+    "REQUEST_PREFS",
+    "REQUEST_THUMB",
+    "REQUEST_FRECENT",
+  ],
   prefs: {
     inPrefs: "REQUEST_PREFS",
     outPrefs: "RECEIVE_PREFS",
-    action_types: new Set(["REQUEST_PREFS"]),
   },
   preview: {
     inThumb: "REQUEST_THUMB",
     outThumb: "RECEIVE_THUMB",
-    action_types: new Set(["REQUEST_THUMB"]),
+  },
+  links: {
+    inFrecent: "REQUEST_FRECENT",
+    outFrecent: "RECEIVE_FRECENT",
+    outPlacesChange: "RECEIVE_PLACES_CHANGE",
   },
 };
 
 let NewTabMessages = {
 
   _prefs: {},
 
   /** NEWTAB EVENT HANDLERS **/
 
-  /*
-   * Return to the originator all newtabpage prefs. A point-to-point request.
-   */
-  handlePrefRequest(actionName, {target}) {
-    if (ACTIONS.prefs.inPrefs === actionName) {
-      let results = NewTabPrefsProvider.prefs.newtabPagePrefs;
-      NewTabWebChannel.send(ACTIONS.prefs.outPrefs, results, target);
+  handleContentRequest(actionName, {data, target}) {
+    switch (actionName) {
+      case ACTIONS.prefs.inPrefs:
+        // Return to the originator all newtabpage prefs
+        let results = NewTabPrefsProvider.prefs.newtabPagePrefs;
+        NewTabWebChannel.send(ACTIONS.prefs.outPrefs, results, target);
+        break;
+      case ACTIONS.preview.inThumb:
+        // Return to the originator a preview URL
+        PreviewProvider.getThumbnail(data).then(imgData => {
+          NewTabWebChannel.send(ACTIONS.preview.outThumb, {url: data, imgData}, target);
+        });
+        break;
+      case ACTIONS.links.inFrecent:
+        // Return to the originator the top frecent links
+        PlacesProvider.links.getLinks().then(links => {
+          NewTabWebChannel.send(ACTIONS.links.outFrecent, links, target);
+        });
+        break;
     }
   },
 
-  handlePreviewRequest(actionName, {data, target}) {
-    if (ACTIONS.preview.inThumb === actionName) {
-      PreviewProvider.getThumbnail(data).then(imgData => {
-        NewTabWebChannel.send(ACTIONS.preview.outThumb, {url: data, imgData}, target);
-      });
-    }
+  /*
+   * Broadcast places change to all open newtab pages
+   */
+  handlePlacesChange(type, data) {
+    NewTabWebChannel.broadcast(ACTIONS.links.outPlacesChange, {type, data});
   },
 
   /*
    * Broadcast preference changes to all open newtab pages
    */
   handlePrefChange(actionName, value) {
     let prefChange = {};
     prefChange[actionName] = value;
@@ -78,47 +100,54 @@ let NewTabMessages = {
         this.uninit();
       } else if (!this._prefs.enabled && value) {
         this.init();
       }
     }
   },
 
   init() {
-    this.handlePrefRequest = this.handlePrefRequest.bind(this);
-    this.handlePreviewRequest = this.handlePreviewRequest.bind(this);
-    this.handlePrefChange = this.handlePrefChange.bind(this);
+    this.handleContentRequest = this.handleContentRequest.bind(this);
     this._handleEnabledChange = this._handleEnabledChange.bind(this);
 
+    PlacesProvider.links.init();
     NewTabPrefsProvider.prefs.init();
     NewTabWebChannel.init();
 
     this._prefs.enabled = Preferences.get(PREF_ENABLED, false);
 
     if (this._prefs.enabled) {
-      NewTabWebChannel.on(ACTIONS.prefs.inPrefs, this.handlePrefRequest);
-      NewTabWebChannel.on(ACTIONS.preview.inThumb, this.handlePreviewRequest);
-
+      for (let action of ACTIONS.inboundActions) {
+        NewTabWebChannel.on(action, this.handleContentRequest);
+      }
       NewTabPrefsProvider.prefs.on(PREF_ENABLED, this._handleEnabledChange);
 
       for (let pref of NewTabPrefsProvider.newtabPagePrefSet) {
         NewTabPrefsProvider.prefs.on(pref, this.handlePrefChange);
       }
+
+      PlacesProvider.links.on("deleteURI", this.handlePlacesChange);
+      PlacesProvider.links.on("clearHistory", this.handlePlacesChange);
+      PlacesProvider.links.on("linkChanged", this.handlePlacesChange);
+      PlacesProvider.links.on("manyLinksChanged", this.handlePlacesChange);
     }
   },
 
   uninit() {
     this._prefs.enabled = Preferences.get(PREF_ENABLED, false);
 
     if (this._prefs.enabled) {
       NewTabPrefsProvider.prefs.off(PREF_ENABLED, this._handleEnabledChange);
 
-      NewTabWebChannel.off(ACTIONS.prefs.inPrefs, this.handlePrefRequest);
-      NewTabWebChannel.off(ACTIONS.prefs.inThumb, this.handlePreviewRequest);
+      for (let action of ACTIONS.inboundActions) {
+        NewTabWebChannel.off(action, this.handleContentRequest);
+      }
+
       for (let pref of NewTabPrefsProvider.newtabPagePrefSet) {
         NewTabPrefsProvider.prefs.off(pref, this.handlePrefChange);
       }
     }
 
+    PlacesProvider.links.uninit();
     NewTabPrefsProvider.prefs.uninit();
     NewTabWebChannel.uninit();
   }
 };

--- a/browser/components/newtab/PlacesProvider.jsm
+++ b/browser/components/newtab/PlacesProvider.jsm
@@ -1,27 +1,24 @@
 /* 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/. */
 
-/* global XPCOMUtils, Services, BinarySearch, PlacesUtils, gPrincipal, EventEmitter */
+/* global XPCOMUtils, Services, PlacesUtils, gPrincipal, EventEmitter */
 /* global gLinks */
 /* exported PlacesProvider */
 
 "use strict";
 
 this.EXPORTED_SYMBOLS = ["PlacesProvider"];
 
 const {interfaces: Ci, utils: Cu} = Components;
 Cu.import("resource://gre/modules/Services.jsm");
 Cu.import("resource://gre/modules/XPCOMUtils.jsm");
 
-XPCOMUtils.defineLazyModuleGetter(this, "BinarySearch",
-  "resource://gre/modules/BinarySearch.jsm");
-
 XPCOMUtils.defineLazyModuleGetter(this, "PlacesUtils",
   "resource://gre/modules/PlacesUtils.jsm");
 
 XPCOMUtils.defineLazyGetter(this, "EventEmitter", function() {
   const {EventEmitter} = Cu.import("resource://devtools/shared/event-emitter.js", {});
   return EventEmitter;
 });
 
@@ -135,24 +132,32 @@ Links.prototype = {
                         Ci.nsISupportsWeakReference])
   },
 
   /**
    * Must be called before the provider is used.
    * Makes it easy to disable under pref
    */
   init: function PlacesProvider_init() {
-    PlacesUtils.history.addObserver(this.historyObserver, true);
+    try {
+      PlacesUtils.history.addObserver(this.historyObserver, true);
+    } catch (e) {
+      Cu.reportError(e);
+    }
   },
 
   /**
    * Must be called before the provider is unloaded.
    */
-  destroy: function PlacesProvider_destroy() {
-    PlacesUtils.history.removeObserver(this.historyObserver);
+  uninit: function PlacesProvider_uninit() {
+    try {
+      PlacesUtils.history.removeObserver(this.historyObserver);
+    } catch (e) {
+      Cu.reportError(e);
+    }
   },
 
   /**
    * Gets the current set of links delivered by this provider.
    *
    * @returns {Promise} Returns a promise with the array of links as payload.
    */
   getLinks: Task.async(function*() {

--- a/browser/components/newtab/tests/browser/browser.ini
+++ b/browser/components/newtab/tests/browser/browser.ini
@@ -1,13 +1,14 @@
 [DEFAULT]
 support-files =
   blue_page.html
   dummy_page.html
   newtabwebchannel_basic.html
+  newtabmessages_places.html
   newtabmessages_prefs.html
   newtabmessages_preview.html
 
 [browser_PreviewProvider.js]
 [browser_remotenewtab_pageloads.js]
 [browser_newtab_overrides.js]
 [browser_newtabmessages.js]
 [browser_newtabwebchannel.js]

--- a/browser/components/newtab/tests/browser/browser_newtabmessages.js
+++ b/browser/components/newtab/tests/browser/browser_newtabmessages.js
@@ -1,17 +1,19 @@
-/* globals Cu, XPCOMUtils, Preferences, is, registerCleanupFunction, NewTabWebChannel */
+/* globals Cu, XPCOMUtils, Preferences, is, registerCleanupFunction, NewTabWebChannel, PlacesTestUtils */
 
 "use strict";
 
 Cu.import("resource://gre/modules/Preferences.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "NewTabWebChannel",
                                   "resource:///modules/NewTabWebChannel.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "NewTabMessages",
                                   "resource:///modules/NewTabMessages.jsm");
+XPCOMUtils.defineLazyModuleGetter(this, "PlacesTestUtils",
+                                  "resource://testing-common/PlacesTestUtils.jsm");
 
 function setup() {
   Preferences.set("browser.newtabpage.enhanced", true);
   Preferences.set("browser.newtabpage.remote.mode", "test");
   Preferences.set("browser.newtabpage.remote", true);
   NewTabMessages.init();
 }
 
@@ -78,8 +80,81 @@ add_task(function* previewMessages_reque
   });
 
   yield BrowserTestUtils.withNewTab(tabOptions, function*() {
     yield previewResponseAck;
   });
   cleanup();
   Services.prefs.setBoolPref("browser.pagethumbnails.capturing_disabled", oldEnabledPref);
 });
+
+/*
+ * Sanity tests for places messages
+ */
+add_task(function* placesMessages_request() {
+  setup();
+  let testURL = "https://example.com/browser/browser/components/newtab/tests/browser/newtabmessages_places.html";
+
+  // url prefix for test history population
+  const TEST_URL = "https://mozilla.com/";
+  // time when the test starts execution
+  const TIME_NOW = (new Date()).getTime();
+
+  // utility function to compute past timestamp
+  function timeDaysAgo(numDays) {
+    return TIME_NOW - (numDays * 24 * 60 * 60 * 1000);
+  }
+
+  // utility function to make a visit for insertion into places db
+  function makeVisit(index, daysAgo, isTyped, domain=TEST_URL) {
+    let {
+      TRANSITION_TYPED,
+      TRANSITION_LINK
+    } = PlacesUtils.history;
+
+    return {
+      uri: NetUtil.newURI(`${domain}${index}`),
+      visitDate: timeDaysAgo(daysAgo),
+      transition: (isTyped) ? TRANSITION_TYPED : TRANSITION_LINK,
+    };
+  }
+
+  yield PlacesTestUtils.clearHistory();
+
+  // all four visits must come from different domains to avoid deduplication
+  let visits = [
+    makeVisit(0, 0, true, "http://bar.com/"), // frecency 200, today
+    makeVisit(1, 0, true, "http://foo.com/"), // frecency 200, today
+    makeVisit(2, 2, true, "http://buz.com/"), // frecency 200, 2 days ago
+    makeVisit(3, 2, false, "http://aaa.com/"), // frecency 10, 2 days ago, transition
+  ];
+
+  yield PlacesTestUtils.addVisits(visits);
+
+  /** Test Begins **/
+
+  let tabOptions = {
+    gBrowser,
+    url: testURL
+  };
+
+  let placesResponseAck = new Promise(resolve => {
+    NewTabWebChannel.once("numItemsAck", (_, msg) => {
+      ok(true, "a request response has been received");
+      is(msg.data, visits.length + 1, "received an expect number of history items");
+      resolve();
+    });
+  });
+
+  yield BrowserTestUtils.withNewTab(tabOptions, function*() {
+    yield placesResponseAck;
+    let placesChangeAck = new Promise(resolve => {
+      NewTabWebChannel.once("clearHistoryAck", (_, msg) => {
+        ok(true, "a change response has been received");
+        is(msg.data, "clearHistory", "a clear history message has been received");
+        resolve();
+      });
+    });
+    yield PlacesTestUtils.clearHistory();
+    yield placesChangeAck;
+  });
+  cleanup();
+});

new file mode 100644
--- /dev/null
+++ b/browser/components/newtab/tests/browser/newtabmessages_places.html
@@ -0,0 +1,49 @@
+<html>
+  <head>
+    <meta charset="utf8">
+    <title>Newtab WebChannel test</title>
+  </head>
+  <body>
+    <script>
+      window.addEventListener("WebChannelMessageToContent", function(e) {
+        if (e.detail.message) {
+          let reply;
+          switch (e.detail.message.type) {
+            case "RECEIVE_FRECENT":
+              reply = new window.CustomEvent("WebChannelMessageToChrome", {
+                detail: {
+                  id: "newtab",
+                  message: JSON.stringify({type: "numItemsAck", data: e.detail.message.data.length}),
+                }
+              });
+              window.dispatchEvent(reply);
+              break;
+            case "RECEIVE_PLACES_CHANGE":
+              if (e.detail.message.data.type === "clearHistory") {
+                reply = new window.CustomEvent("WebChannelMessageToChrome", {
+                  detail: {
+                    id: "newtab",
+                    message: JSON.stringify({type: "clearHistoryAck", data: e.detail.message.data.type}),
+                  }
+                });
+                window.dispatchEvent(reply);
+              }
+              break;
+          }
+        }
+      }, true);
+
+      document.onreadystatechange = function () {
+        if (document.readyState === "complete") {
+          let msg = new window.CustomEvent("WebChannelMessageToChrome", {
+            detail: {
+              id: "newtab",
+              message: JSON.stringify({type: "REQUEST_FRECENT"}),
+            }
+          });
+          window.dispatchEvent(msg);
+        }
+      }
+    </script>
+  </body>
+</html>

--- a/browser/components/newtab/tests/xpcshell/test_PlacesProvider.js
+++ b/browser/components/newtab/tests/xpcshell/test_PlacesProvider.js
@@ -165,17 +165,17 @@ add_task(function* test_Links_onLinkChan
   });
 
   // add a visit
   let testURI = NetUtil.newURI(url);
   yield PlacesTestUtils.addVisits(testURI);
   yield linkChangedPromise;
 
   yield PlacesTestUtils.clearHistory();
-  provider.destroy();
+  provider.uninit();
 });
 
 add_task(function* test_Links_onClearHistory() {
   let provider = PlacesProvider.links;
   provider.init();
 
   let clearHistoryPromise = new Promise(resolve => {
     let handler = () => {
@@ -189,17 +189,17 @@ add_task(function* test_Links_onClearHis
   // add visits
   for (let i = 0; i <= 10; i++) {
     let url = `https://example.com/onClearHistory${i}`;
     let testURI = NetUtil.newURI(url);
     yield PlacesTestUtils.addVisits(testURI);
   }
   yield PlacesTestUtils.clearHistory();
   yield clearHistoryPromise;
-  provider.destroy();
+  provider.uninit();
 });
 
 add_task(function* test_Links_onDeleteURI() {
   let provider = PlacesProvider.links;
   provider.init();
 
   let testURL = "https://example.com/toDelete";
 
@@ -212,17 +212,17 @@ add_task(function* test_Links_onDeleteUR
 
     provider.on("deleteURI", handler);
   });
 
   let testURI = NetUtil.newURI(testURL);
   yield PlacesTestUtils.addVisits(testURI);
   yield PlacesUtils.history.remove(testURL);
   yield deleteURIPromise;
-  provider.destroy();
+  provider.uninit();
 });
 
 add_task(function* test_Links_onManyLinksChanged() {
   let provider = PlacesProvider.links;
   provider.init();
 
   let promise = new Promise(resolve => {
     let handler = () => {
@@ -238,17 +238,17 @@ add_task(function* test_Links_onManyLink
   let testURI = NetUtil.newURI(testURL);
   yield PlacesTestUtils.addVisits(testURI);
 
   // trigger DecayFrecency
   PlacesUtils.history.QueryInterface(Ci.nsIObserver).
     observe(null, "idle-daily", "");
 
   yield promise;
-  provider.destroy();
+  provider.uninit();
 });
 
 add_task(function* test_Links_execute_query() {
   yield PlacesTestUtils.clearHistory();
   let provider = PlacesProvider.links;
 
   let visits = [
     makeVisit(0, 0, true), // frecency 200, today