--- a/services/sync/modules/engines/bookmarks.js
+++ b/services/sync/modules/engines/bookmarks.js
@@ -41,16 +41,21 @@ const {
 } = Ci.nsINavBookmarksService;
 
 const SQLITE_MAX_VARIABLE_NUMBER = 999;
 
 const ORGANIZERQUERY_ANNO = "PlacesOrganizer/OrganizerQuery";
 const ALLBOOKMARKS_ANNO = "AllBookmarks";
 const MOBILE_ANNO = "MobileBookmarks";
 
+// The number of seconds between cleanup runs, when we delete and upload
+// tombstones for unexpected items on the server. Defaults to once every
+// two weeks.
+const CLEANUP_INTERVAL_SECONDS = 2 * 7 * 86400;
+
 // The tracker ignores changes made by bookmark import and restore, and
 // changes made by Sync. We don't need to exclude `SOURCE_IMPORT`, but both
 // import and restore fire `bookmarks-restore-*` observer notifications, and
 // the tracker doesn't currently distinguish between the two.
 const IGNORED_SOURCES = [SOURCE_SYNC, SOURCE_IMPORT, SOURCE_IMPORT_REPLACE];
 
 // Returns the constructor for a bookmark record type.
 function getTypeObject(type) {
@@ -242,16 +247,17 @@ BookmarkSeparator.prototype = {
     this.pos = item.index;
   },
 };
 
 Utils.deferGetSet(BookmarkSeparator, "cleartext", "pos");
 
 this.BookmarksEngine = function BookmarksEngine(service) {
   SyncEngine.call(this, "Bookmarks", service);
+  this._wasCleanedUp = false;
 }
 BookmarksEngine.prototype = {
   __proto__: SyncEngine.prototype,
   _recordObj: PlacesItem,
   _storeObj: BookmarksStore,
   _trackerObj: BookmarksTracker,
   version: 2,
   _defaultSort: "index",
@@ -535,16 +541,29 @@ BookmarksEngine.prototype = {
       } finally {
         // Reorder children.
         this._store._orderChildren();
         delete this._store._childrenToOrder;
       }
     }
   },
 
+  _uploadOutgoing() {
+    try {
+      SyncEngine.prototype._uploadOutgoing.call(this);
+      if (this._wasCleanedUp) {
+        // Update the last cleanup timestamp. If `_uploadOutgoing` throws,
+        // we'll try cleaning up again on the next sync.
+        this.lastCleanup = this.lastSync;
+      }
+    } finally {
+      this._wasCleanedUp = false;
+    }
+  },
+
   _syncFinish: function _syncFinish() {
     SyncEngine.prototype._syncFinish.call(this);
     this._tracker._ensureMobileQuery();
   },
 
   _syncCleanup: function _syncCleanup() {
     SyncEngine.prototype._syncCleanup.call(this);
     delete this._guidMap;
@@ -703,17 +722,75 @@ BookmarksEngine.prototype = {
 
     // The local, duplicate ID is always deleted on the server - but for
     // bookmarks it is a logical delete.
     // Simply adding this (now non-existing) ID to the tracker is enough.
     this._modified.set(localDupeGUID, { modified: now, deleted: true });
   },
   getValidator() {
     return new BookmarkValidator();
-  }
+  },
+
+  get lastCleanup() {
+    let asString = Svc.Prefs.get("bookmarks.lastCleanup");
+    let value = parseFloat(asString);
+    return Number.isFinite(value) ? value : Infinity;
+  },
+
+  set lastCleanup(value) {
+    Svc.Prefs.set("bookmarks.lastCleanup", value.toString());
+  },
+
+  _needsCleanup() {
+    return this.lastSync &&
+           this.lastCleanup < this._tracker._now() - CLEANUP_INTERVAL_SECONDS;
+  },
+
+  fetchOutgoingRecords() {
+    let records = SyncEngine.prototype.fetchOutgoingRecords.call(this);
+    if (!this._needsCleanup()) {
+      return records;
+    }
+
+    this._wasCleanedUp = true;
+
+    // Fetch tombstones and deletions for items that shouldn't be on the server,
+    // and add them to our queue of outgoing records.
+    let nonSyncableEntries = Async.promiseSpinningly(
+      PlacesSyncUtils.bookmarks.fetchNonSyncableEntries());
+    for (let info of nonSyncableEntries) {
+      // Unconditionally delete items that don't require tombstones. These
+      // will be deleted from the server at the end of the sync.
+      if (!info.needsTombstone) {
+        this._log.trace("Deleting non-syncable item " +
+                        info.syncId);
+        this._deleteId(info.syncId);
+        continue;
+      }
+
+      // Create tombstone records for items that should be removed from other
+      // clients. We can't use `_createRecord` here, because it'll fetch the
+      // existing item from the local store.
+      this._log.trace("Uploading tombstone for non-syncable item " +
+                      info.syncId);
+      try {
+        let record = this._store.createTombstone(info.syncId, this.name);
+        record.encrypt(this.service.collectionKeys.keyForCollection(this.name));
+        records.push(record);
+      } catch (ex) {
+        if (Async.isShutdownException(ex)) {
+          throw ex;
+        }
+        this._log.warn("Error encrypting tombstone for non-syncable item " +
+                       info.syncId, ex);
+      }
+    }
+
+    return records;
+  },
 };
 
 function BookmarksStore(name, engine) {
   Store.call(this, name, engine);
   this._foldersToDelete = new Set();
   this._atomsToDelete = new Set();
   // Explicitly nullify our references to our cached services so we don't leak
   Svc.Obs.add("places-shutdown", function() {
@@ -954,34 +1031,38 @@ BookmarksStore.prototype = {
 
     Async.promiseSpinningly(PlacesSyncUtils.bookmarks.changeGuid(oldID, newID));
   },
 
   // Create a record starting from the weave id (places guid)
   createRecord: function createRecord(id, collection) {
     let item = Async.promiseSpinningly(PlacesSyncUtils.bookmarks.fetch(id));
     if (!item) { // deleted item
-      let record = new PlacesItem(collection, id);
-      record.deleted = true;
-      return record;
+      return this.createTombstone(id, collection);
     }
 
     let recordObj = getTypeObject(item.kind);
     if (!recordObj) {
       this._log.warn("Unknown item type, cannot serialize: " + item.kind);
       recordObj = PlacesItem;
     }
     let record = new recordObj(collection, id);
     record.fromSyncBookmark(item);
 
     record.sortindex = this._calculateIndex(record);
 
     return record;
   },
 
+  createTombstone(id, collection) {
+    let record = new PlacesItem(collection, id);
+    record.deleted = true;
+    return record;
+  },
+
   _stmts: {},
   _getStmt: function(query) {
     if (query in this._stmts) {
       return this._stmts[query];
     }
 
     this._log.trace("Creating SQL statement: " + query);
     let db = PlacesUtils.history.QueryInterface(Ci.nsPIPlacesDatabase)

--- a/services/sync/tests/unit/test_bookmark_engine.js
+++ b/services/sync/tests/unit/test_bookmark_engine.js
@@ -7,27 +7,135 @@ Cu.import("resource://gre/modules/Bookma
 Cu.import("resource://gre/modules/Log.jsm");
 Cu.import("resource://services-sync/constants.js");
 Cu.import("resource://services-sync/engines.js");
 Cu.import("resource://services-sync/engines/bookmarks.js");
 Cu.import("resource://services-sync/service.js");
 Cu.import("resource://services-sync/util.js");
 Cu.import("resource://testing-common/services/sync/utils.js");
 Cu.import("resource://gre/modules/Promise.jsm");
+Cu.import("resource:///modules/PlacesUIUtils.jsm");
 
 initTestLogging("Trace");
 
 Service.engineManager.register(BookmarksEngine);
 
 function* assertChildGuids(folderGuid, expectedChildGuids, message) {
   let tree = yield PlacesUtils.promiseBookmarksTree(folderGuid);
   let childGuids = tree.children.map(child => child.guid);
   deepEqual(childGuids, expectedChildGuids, message);
 }
 
+add_task(function* test_cleanup() {
+  _("Ensure we periodically clean up items that shouldn't be on the server.");
+
+  let engine  = new BookmarksEngine(Service);
+  let store   = engine._store;
+  let tracker = engine._tracker;
+  let server = serverForFoo(engine);
+  new SyncTestingInfrastructure(server.server);
+
+  let collection = server.user("foo").collection("bookmarks");
+
+  // The `leftPaneFolderId` getter creates the root and queries as a side
+  // effect.
+  let leftPaneRootGUID = yield PlacesUtils.promiseItemGuid(PlacesUIUtils.leftPaneFolderId);
+  _(`Upload left pane root: ${leftPaneRootGUID}`);
+  {
+    let record = collection.insert(leftPaneRootGUID, store.createRecord(leftPaneRootGUID));
+    record.modified = Date.now() / 1000 - 60 * 10;
+  }
+
+  let leftPaneQueryGUIDs = [];
+  for (let [name, id] of Object.entries(PlacesUIUtils.leftPaneQueries)) {
+    let guid = yield PlacesUtils.promiseItemGuid(id);
+    _(`Uploading left pane query for ${name}: ${guid}`);
+    let record = collection.insert(guid, store.createRecord(guid));
+    record.modified = Date.now() / 1000 - 60 * 10;
+    leftPaneQueryGUIDs.push(guid);
+  }
+
+  _("Upload the Places root");
+  {
+    let record = collection.insert("places", store.createRecord("places"));
+    record.modified = Date.now() / 1000 - 60 * 10;
+  }
+
+  _("Create a local custom root");
+  let customRoot = yield PlacesUtils.bookmarks.insert({
+    type: PlacesUtils.bookmarks.TYPE_FOLDER,
+    parentGuid: PlacesUtils.bookmarks.rootGuid,
+    title: "Custom root",
+  });
+  let customRootChild = yield PlacesUtils.bookmarks.insert({
+    parentGuid: customRoot.guid,
+    title: "Child of custom root",
+    url: "https://example.com",
+  });
+
+  _(`Upload custom root ${customRoot.guid} and child ${customRootChild.guid}`);
+  {
+    let rootRecord = collection.insert(customRoot.guid,
+      store.createRecord(customRoot.guid));
+    rootRecord.modified = Date.now() / 1000 - 60 * 10;
+
+    let childRecord = collection.insert(customRootChild.guid,
+      store.createRecord(customRootChild.guid));
+    childRecord.modified = Date.now() / 1000 - 60 * 10;
+  }
+
+  Svc.Obs.notify("weave:engine:start-tracking");
+
+  try {
+    // Make the last sync time later than the roots on the server, so that we
+    // don't try to download and apply them.
+    engine.lastSync = Date.now() / 1000 - 60;
+
+    let recentCleanup = Date.now() / 1000;
+    Svc.Prefs.set("bookmarks.lastCleanup", recentCleanup.toString());
+
+    yield sync_engine_and_validate_telem(engine, false);
+
+    equal(parseFloat(Svc.Prefs.get("bookmarks.lastCleanup")), recentCleanup,
+      "Last cleanup time shouldn't change if we've cleaned up recently");
+
+    deepEqual(collection.keys().sort(), [
+      "places",
+      customRoot.guid,
+      customRootChild.guid,
+      leftPaneRootGUID,
+      ...leftPaneQueryGUIDs
+    ].sort(), "Non-syncable items should remain on the server without cleanup");
+
+    let oldCleanup = Date.now() / 1000 - 3 * 7 * 86400;
+    Svc.Prefs.set("bookmarks.lastCleanup", oldCleanup.toString());
+
+    yield sync_engine_and_validate_telem(engine, false);
+
+    ok(parseFloat(Svc.Prefs.get("bookmarks.lastCleanup")) > oldCleanup,
+      "Should update last cleanup time after cleaning up");
+
+    let expected = [leftPaneRootGUID, ...leftPaneQueryGUIDs].sort();
+    deepEqual(collection.keys().sort(), expected,
+      "Custom roots and Places root should be deleted from the server");
+
+    for (let guid of expected) {
+      let contents = JSON.parse(collection.wbo(guid).data.ciphertext);
+      equal(contents.id, guid, `Tombstone GUIDs should match`);
+      ok(contents.deleted, `Tombstone should exist for ${guid} on the server`);
+    }
+  } finally {
+    store.wipe();
+    Svc.Prefs.resetBranch("");
+    Service.recordManager.clearCache();
+    yield new Promise(resolve => server.stop(resolve));
+    Svc.Obs.notify("weave:engine:stop-tracking");
+  }
+});
+
 add_task(function* test_change_during_sync() {
   _("Ensure that we track changes made during a sync.");
 
   let engine  = new BookmarksEngine(Service);
   let store   = engine._store;
   let tracker = engine._tracker;
   let server = serverForFoo(engine);
   new SyncTestingInfrastructure(server.server);

--- a/toolkit/components/places/PlacesSyncUtils.jsm
+++ b/toolkit/components/places/PlacesSyncUtils.jsm
@@ -26,16 +26,19 @@ XPCOMUtils.defineLazyModuleGetter(this, 
  * records. The calls are similar to those in `Bookmarks.jsm` and
  * `nsINavBookmarksService`, with special handling for smart bookmarks,
  * tags, keywords, synced annotations, and missing parents.
  */
 var PlacesSyncUtils = {};
 
 const { SOURCE_SYNC } = Ci.nsINavBookmarksService;
 
+const ORGANIZER_FOLDER_ANNO = "PlacesOrganizer/OrganizerFolder";
+const ORGANIZER_QUERY_ANNO = "PlacesOrganizer/OrganizerQuery";
+
 // These are defined as lazy getters to defer initializing the bookmarks
 // service until it's needed.
 XPCOMUtils.defineLazyGetter(this, "ROOT_SYNC_ID_TO_GUID", () => ({
   menu: PlacesUtils.bookmarks.menuGuid,
   places: PlacesUtils.bookmarks.rootGuid,
   tags: PlacesUtils.bookmarks.tagsGuid,
   toolbar: PlacesUtils.bookmarks.toolbarGuid,
   unfiled: PlacesUtils.bookmarks.unfiledGuid,
@@ -89,16 +92,67 @@ const BookmarkSyncUtils = PlacesSyncUtil
   /**
    * Converts a Sync record ID to a Places GUID.
    */
   syncIdToGuid(syncId) {
     return ROOT_SYNC_ID_TO_GUID[syncId] || syncId;
   },
 
   /**
+   * Fetches an array of `{ syncId, needsTombstone }` tuples for all
+   * non-syncable items. This includes the Places root, custom roots, tags, left
+   * pane items, and other items outside the four synced roots.
+   *
+   * `needsTombstone` indicates whether the bookmarks engine should upload a
+   * tombstone record for the item. This is true for left pane queries, so
+   * that they can be removed from other clients if we mistakenly uploaded them
+   * in the past. For other items, `needsTombstone` is false: we'll remove the
+   * records from the server, but keep them on existing clients.
+   *
+   * Sync calls this method to periodically clean up records that shouldn't be
+   * on the server.
+   */
+  fetchNonSyncableEntries: Task.async(function* () {
+    let db = yield PlacesUtils.promiseDBConnection();
+
+    let rows = yield db.executeCached(`
+      WITH RECURSIVE
+      syncedItems(id) AS (
+        SELECT b.id FROM moz_bookmarks b
+        WHERE b.guid IN (:menuGuid, :toolbarGuid, :unfiledGuid, :mobileGuid)
+        UNION ALL
+        SELECT b.id FROM moz_bookmarks b
+        JOIN syncedItems s ON b.parent = s.id
+      )
+      SELECT b.guid, IFNULL(
+        (SELECT 1 FROM moz_items_annos a
+         JOIN moz_anno_attributes n ON a.anno_attribute_id = n.id
+         WHERE n.name IN (:leftPaneFolder, :leftPaneQuery) AND
+               a.item_id = b.id
+        ), 0) AS needsTombstone
+      FROM moz_bookmarks b
+      LEFT JOIN syncedItems s ON b.id = s.id
+      WHERE s.id IS NULL`,
+      { menuGuid: PlacesUtils.bookmarks.menuGuid,
+        toolbarGuid: PlacesUtils.bookmarks.toolbarGuid,
+        unfiledGuid: PlacesUtils.bookmarks.unfiledGuid,
+        mobileGuid: PlacesUtils.bookmarks.mobileGuid,
+        leftPaneFolder: ORGANIZER_FOLDER_ANNO,
+        leftPaneQuery: ORGANIZER_QUERY_ANNO });
+
+    return rows.map(row => {
+      let guid = row.getResultByName("guid");
+      return {
+        syncId: BookmarkSyncUtils.guidToSyncId(guid),
+        needsTombstone: !!row.getResultByName("needsTombstone"),
+      };
+    });
+  }),
+
+  /**
    * Fetches the sync IDs for a folder's children, ordered by their position
    * within the folder.
    */
   fetchChildSyncIds: Task.async(function* (parentSyncId) {
     PlacesUtils.SYNC_BOOKMARK_VALIDATORS.syncId(parentSyncId);
     let parentGuid = BookmarkSyncUtils.syncIdToGuid(parentSyncId);
 
     let db = yield PlacesUtils.promiseDBConnection();