--- a/browser/components/places/content/browserPlacesViews.js
+++ b/browser/components/places/content/browserPlacesViews.js
@@ -1026,52 +1026,76 @@ PlacesToolbar.prototype = {
     }
 
     PlacesViewBase.prototype.uninit.apply(this, arguments);
   },
 
   _openedMenuButton: null,
   _allowPopupShowing: true,
 
-  _rebuild: function PT__rebuild() {
+  get _isAlive() {
+    return this._resultNode && this._rootElt;
+  },
+
+  async _rebuild() {
     // Clear out references to existing nodes, since they will be removed
     // and re-added.
     if (this._overFolder.elt)
       this._clearOverFolder();
 
     this._openedMenuButton = null;
     while (this._rootElt.hasChildNodes()) {
       this._rootElt.firstChild.remove();
     }
 
-    let fragment = document.createDocumentFragment();
     let cc = this._resultNode.childCount;
     if (cc > 0) {
       // There could be a lot of nodes, but we only want to build the ones that
-      // are likely to be shown, not all of them. Then we'll lazily create the
-      // missing nodes when needed.
-      // We don't want to cause reflows at every node insertion to calculate
-      // a precise size, thus we guess a size from the first node.
-      let button = this._insertNewItem(this._resultNode.getChild(0),
-                                       this._rootElt);
-      requestAnimationFrame(() => {
-        // May have been destroyed in the meanwhile.
-        if (!this._resultNode || !this._rootElt)
-          return;
-        // We assume a button with just the icon will be more or less a square,
-        // then compensate the measurement error by considering a larger screen
-        // width. Moreover the window could be bigger than the screen.
-        let size = button.clientHeight;
-        let limit = Math.min(cc, parseInt((window.screen.width * 1.5) / size));
-        for (let i = 1; i < limit; ++i) {
-          this._insertNewItem(this._resultNode.getChild(i), fragment);
+      // are more likely to be shown, not all of them.
+      // We also don't want to wait for reflows at every node insertion, to
+      // calculate a precise number of visible items, thus we guess a size from
+      // the first non-separator node (because separators have flexible size).
+      let startIndex = 0;
+      let limit = await new Promise(resolve => window.requestAnimationFrame(() => {
+        if (!this._isAlive)
+          return resolve(cc);
+
+        // Look for the first non-separator node.
+        let elt;
+        while (startIndex < cc) {
+          elt = this._insertNewItem(this._resultNode.getChild(startIndex),
+                                    this._rootElt);
+          ++startIndex;
+          if (elt.localName != "toolbarseparator")
+            break;
         }
-        this._rootElt.appendChild(fragment);
+        if (!elt)
+          return resolve(cc);
+
+        return window.promiseDocumentFlushed(() => {
+          // We assume a button with just the icon will be more or less a square,
+          // then compensate the measurement error by considering a larger screen
+          // width. Moreover the window could be bigger than the screen.
+          let size = elt.clientHeight || 1; // Sanity fallback.
+          resolve(Math.min(cc, parseInt((window.screen.width * 1.5) / size)));
+        });
+      }));
 
-        this.updateNodesVisibility();
+      if (!this._isAlive)
+        return;
+
+      let fragment = document.createDocumentFragment();
+      for (let i = startIndex; i < limit; ++i) {
+        this._insertNewItem(this._resultNode.getChild(i), fragment);
+      }
+      window.requestAnimationFrame(() => {
+        if (this._isAlive) {
+          this._rootElt.appendChild(fragment);
+          this.updateNodesVisibility();
+        }
       });
     }
 
     if (this._chevronPopup.hasAttribute("type")) {
       // Chevron has already been initialized, but since we are forcing
       // a rebuild of the toolbar, it has to be rebuilt.
       // Otherwise, it will be initialized when the toolbar overflows.
       this._chevronPopup.place = this.place;
@@ -1472,17 +1496,17 @@ PlacesToolbar.prototype = {
   invalidateContainer: function PT_invalidateContainer(aPlacesNode) {
     let elt = this._getDOMNodeForPlacesNode(aPlacesNode, true);
     // Nothing to do if it's a never-visible node.
     if (!elt)
       return;
 
     if (elt == this._rootElt) {
       // Container is the toolbar itself.
-      this._rebuild();
+      this._rebuild().catch(Cu.reportError);
       return;
     }
 
     PlacesViewBase.prototype.invalidateContainer.apply(this, arguments);
   },
 
   _overFolder: { elt: null,
                  openTimer: null,

--- a/browser/components/places/tests/browser/browser_toolbar_overflow.js
+++ b/browser/components/places/tests/browser/browser_toolbar_overflow.js
@@ -34,28 +34,28 @@ add_task(async function setup() {
     if (wasCollapsed) {
       await promiseSetToolbarVisibility(gToolbar, false);
     }
     await PlacesUtils.bookmarks.eraseEverything();
     await PlacesUtils.history.clear();
   });
 });
 
-add_task(async function() {
+add_task(async function test_overflow() {
   // Check that the overflow chevron is visible.
   Assert.ok(!gChevron.collapsed, "The overflow chevron should be visible");
   Assert.ok(gToolbarContent.childNodes.length < BOOKMARKS_COUNT,
             "Not all the nodes should be built by default");
   let visibleNodes = [];
   for (let node of gToolbarContent.childNodes) {
     if (node.style.visibility == "visible")
       visibleNodes.push(node);
   }
   Assert.ok(visibleNodes.length < gToolbarContent.childNodes.length,
-            "The number of visible nodes should be smaller than the number of built nodes");
+            `The number of visible nodes (${visibleNodes.length}) should be smaller than the number of built nodes (${gToolbarContent.childNodes.length})`);
 
   await test_index("Node at the last visible index", visibleNodes.length - 1, "visible");
   await test_index("Node at the first invisible index", visibleNodes.length, "hidden");
   await test_index("First non-built node", gToolbarContent.childNodes.length, undefined);
   await test_index("Later non-built node", gToolbarContent.childNodes.length + 1, undefined);
 
   await test_move_index("Move node from last visible to first hidden",
                         visibleNodes.length - 1, visibleNodes.length,
@@ -63,16 +63,40 @@ add_task(async function() {
   await test_move_index("Move node from fist visible to last built",
                         0, gToolbarContent.childNodes.length - 1,
                         "visible", "hidden");
   await test_move_index("Move node from fist visible to first non built",
                         0, gToolbarContent.childNodes.length,
                         "visible", undefined);
 });
 
+add_task(async function test_separator_first() {
+  // Check that if a separator is the first node, we still calculate overflow
+  // properly.
+  let bm = await PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+    type: PlacesUtils.bookmarks.TYPE_SEPARATOR,
+    index: 0
+  });
+  // Hide and show the toolbar to cause a rebuild.
+  let promiseReady = BrowserTestUtils.waitForEvent(gToolbar, "BookmarksToolbarVisibilityUpdated");
+  await promiseSetToolbarVisibility(gToolbar, false);
+  await promiseReady;
+  promiseReady = BrowserTestUtils.waitForEvent(gToolbar, "BookmarksToolbarVisibilityUpdated");
+  await promiseSetToolbarVisibility(gToolbar, true);
+  await promiseReady;
+
+  let children = gToolbarContent.childNodes;
+  Assert.ok(children.length > 2, "Multiple elements are visible");
+  Assert.equal(children[1]._placesNode.uri, "http://test.places.0/", "Found the first bookmark");
+  Assert.equal(children[1].style.visibility, "visible", "The first bookmark is visible");
+
+  await PlacesUtils.bookmarks.remove(bm);
+});
+
 add_task(async function test_newWindow_noOverflow() {
   info("Check toolbar in a new widow when it was already visible and not overflowed");
   await PlacesUtils.bookmarks.eraseEverything();
   // Add a single bookmark.
   await PlacesUtils.bookmarks.insert({
     parentGuid: PlacesUtils.bookmarks.toolbarGuid,
     url: "http://toolbar.overflow/",
     title: "Example"
@@ -206,8 +230,38 @@ async function test_move_index(desc, fro
                `The bookmark node should be ${original}`);
   if (existingGuid) {
     Assert.equal(children[toIndex]._placesNode.bookmarkGuid, existingGuid,
                  "Found the pushed away bookmark at the expected position");
   }
   Assert.equal(children.length, originalLen,
                "Number of built nodes should stay the same");
 }
+
+add_task(async function test_separator_first() {
+  // Check that if there are only separators, we still show nodes properly.
+  await PlacesUtils.bookmarks.eraseEverything();
+
+  await PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+    type: PlacesUtils.bookmarks.TYPE_SEPARATOR,
+    index: 0
+  });
+  await PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+    type: PlacesUtils.bookmarks.TYPE_SEPARATOR,
+    index: 0
+  });
+  // Hide and show the toolbar to cause a rebuild.
+  let promiseReady = BrowserTestUtils.waitForEvent(gToolbar, "BookmarksToolbarVisibilityUpdated");
+  await promiseSetToolbarVisibility(gToolbar, false);
+  await promiseReady;
+  promiseReady = BrowserTestUtils.waitForEvent(gToolbar, "BookmarksToolbarVisibilityUpdated");
+  await promiseSetToolbarVisibility(gToolbar, true);
+  await promiseReady;
+
+  let children = gToolbarContent.childNodes;
+  Assert.equal(children.length, 2, "The expected elements are visible");
+  Assert.equal(children[0].style.visibility, "visible", "The first bookmark is visible");
+  Assert.equal(children[1].style.visibility, "visible", "The second bookmark is visible");
+
+  await PlacesUtils.bookmarks.eraseEverything();
+});