--- a/services/sync/modules-testing/fakeservices.js
+++ b/services/sync/modules-testing/fakeservices.js
@@ -45,17 +45,19 @@ this.fakeSHA256HMAC = function fakeSHA25
    }
    return message;
 }
 
 this.FakeGUIDService = function FakeGUIDService() {
   let latestGUID = 0;
 
   Utils.makeGUID = function makeGUID() {
-    return "fake-guid-" + latestGUID++;
+    // ensure that this always returns a unique 12 character string
+    let nextGUID = "fake-guid-" + String(latestGUID++).padStart(2, "0");
+    return nextGUID.slice(nextGUID.length-12, nextGUID.length);
   };
 }
 
 /*
  * Mock implementation of WeaveCrypto. It does not encrypt or
  * decrypt, merely returning the input verbatim.
  */
 this.FakeCryptoService = function FakeCryptoService() {

--- a/services/sync/modules/engines/bookmarks.js
+++ b/services/sync/modules/engines/bookmarks.js
@@ -735,24 +735,24 @@ BookmarksStore.prototype = {
     // null, -1 -- all compare false for > 0, so this catches them all. We
     // don't just use <= without the !, because undefined and null compare
     // false for that, too!
     if (!(record._parent > 0)) {
       this._log.debug("Parent is " + record._parent + "; reparenting to unfiled.");
       record._parent = kSpecialIds.unfiled;
     }
 
-    let newId;
     switch (record.type) {
     case "bookmark":
     case "query":
     case "microsummary": {
       let uri = Utils.makeURI(record.bmkUri);
-      newId = PlacesUtils.bookmarks.insertBookmark(
-        record._parent, uri, PlacesUtils.bookmarks.DEFAULT_INDEX, record.title);
+      let newId = PlacesUtils.bookmarks.insertBookmark(
+        record._parent, uri, PlacesUtils.bookmarks.DEFAULT_INDEX, record.title,
+        record.id);
       this._log.debug("created bookmark " + newId + " under " + record._parent
                       + " as " + record.title + " " + record.bmkUri);
 
       // Smart bookmark annotations are strings.
       if (record.queryId) {
         PlacesUtils.annotations.setItemAnnotation(
           newId, SMART_BOOKMARKS_ANNO, record.queryId, 0,
           PlacesUtils.annotations.EXPIRE_NEVER);
@@ -770,30 +770,31 @@ BookmarksStore.prototype = {
 
       if (record.loadInSidebar) {
         PlacesUtils.annotations.setItemAnnotation(
           newId, SIDEBAR_ANNO, true, 0,
           PlacesUtils.annotations.EXPIRE_NEVER);
       }
 
     } break;
-    case "folder":
-      newId = PlacesUtils.bookmarks.createFolder(
-        record._parent, record.title, PlacesUtils.bookmarks.DEFAULT_INDEX);
+    case "folder": {
+      let newId = PlacesUtils.bookmarks.createFolder(
+        record._parent, record.title, PlacesUtils.bookmarks.DEFAULT_INDEX,
+        record.id);
       this._log.debug("created folder " + newId + " under " + record._parent
                       + " as " + record.title);
 
       if (record.description) {
         PlacesUtils.annotations.setItemAnnotation(
           newId, DESCRIPTION_ANNO, record.description, 0,
           PlacesUtils.annotations.EXPIRE_NEVER);
       }
 
       // record.children will be dealt with in _orderChildren.
-      break;
+    } break;
     case "livemark":
       let siteURI = null;
       if (!record.feedUri) {
         this._log.debug("No feed URI: skipping livemark record " + record.id);
         return;
       }
       if (PlacesUtils.annotations
                      .itemHasAnnotation(record._parent, PlacesUtils.LMANNO_FEEDURI)) {
@@ -828,35 +829,29 @@ BookmarksStore.prototype = {
       }
 
       this._log.debug("Created livemark " + livemark.id + " under " +
                       livemark.parentId + " as " + livemark.title +
                       ", " + livemark.siteURI.spec + ", " +
                       livemark.feedURI.spec + ", GUID " +
                       livemark.guid);
       break;
-    case "separator":
-      newId = PlacesUtils.bookmarks.insertSeparator(
-        record._parent, PlacesUtils.bookmarks.DEFAULT_INDEX);
+    case "separator": {
+      let newId = PlacesUtils.bookmarks.insertSeparator(
+        record._parent, PlacesUtils.bookmarks.DEFAULT_INDEX, record.id);
       this._log.debug("created separator " + newId + " under " + record._parent);
-      break;
+    } break;
     case "item":
       this._log.debug(" -> got a generic places item.. do nothing?");
       return;
     default:
       this._log.error("_create: Unknown item type: " + record.type);
       return;
     }
 
-    if (newId) {
-      // Livemarks can set the GUID through the API, so there's no need to
-      // do that here.
-      this._log.trace("Setting GUID of new item " + newId + " to " + record.id);
-      this._setGUID(newId, record.id);
-    }
   },
 
   // Factored out of `remove` to avoid redundant DB queries when the Places ID
   // is already known.
   removeById: function removeById(itemId, guid) {
     let type = PlacesUtils.bookmarks.getItemType(itemId);
 
     switch (type) {

--- a/services/sync/tests/unit/test_bookmark_order.js
+++ b/services/sync/tests/unit/test_bookmark_order.js
@@ -70,69 +70,75 @@ function run_test() {
   }
 
   function apply(record) {
     store._childrenToOrder = {};
     store.applyIncoming(record);
     store._orderChildren();
     delete store._childrenToOrder;
   }
-
+  let id10 = "10_aaaaaaaaa";
   _("basic add first bookmark");
-  apply(bookmark("10", ""));
-  check(["10"]);
-
+  apply(bookmark(id10, ""));
+  check([id10]);
+  let id20 = "20_aaaaaaaaa";
   _("basic append behind 10");
-  apply(bookmark("20", ""));
-  check(["10", "20"]);
+  apply(bookmark(id20, ""));
+  check([id10, id20]);
 
+  let id31 = "31_aaaaaaaaa";
+  let id30 = "f30_aaaaaaaa";
   _("basic create in folder");
-  apply(bookmark("31", "f30"));
-  let f30 = folder("f30", "", ["31"]);
+  apply(bookmark(id31, id30));
+  let f30 = folder(id30, "", [id31]);
   apply(f30);
-  check(["10", "20", ["31"]]);
+  check([id10, id20, [id31]]);
 
+  let id41 = "41_aaaaaaaaa";
+  let id40 = "f40_aaaaaaaa";
   _("insert missing parent -> append to unfiled");
-  apply(bookmark("41", "f40"));
-  check(["10", "20", ["31"], "41"]);
+  apply(bookmark(id41, id40));
+  check([id10, id20, [id31], id41]);
+
+  let id42 = "42_aaaaaaaaa";
 
   _("insert another missing parent -> append");
-  apply(bookmark("42", "f40"));
-  check(["10", "20", ["31"], "41", "42"]);
+  apply(bookmark(id42, id40));
+  check([id10, id20, [id31], id41, id42]);
 
   _("insert folder -> move children and followers");
-  let f40 = folder("f40", "", ["41", "42"]);
+  let f40 = folder(id40, "", [id41, id42]);
   apply(f40);
-  check(["10", "20", ["31"], ["41", "42"]]);
+  check([id10, id20, [id31], [id41, id42]]);
 
   _("Moving 41 behind 42 -> update f40");
-  f40.children = ["42", "41"];
+  f40.children = [id42, id41];
   apply(f40);
-  check(["10", "20", ["31"], ["42", "41"]]);
+  check([id10, id20, [id31], [id42, id41]]);
 
   _("Moving 10 back to front -> update 10, 20");
-  f40.children = ["41", "42"];
+  f40.children = [id41, id42];
   apply(f40);
-  check(["10", "20", ["31"], ["41", "42"]]);
+  check([id10, id20, [id31], [id41, id42]]);
 
   _("Moving 20 behind 42 in f40 -> update 50");
-  apply(bookmark("20", "f40"));
-  check(["10", ["31"], ["41", "42", "20"]]);
+  apply(bookmark(id20, id40));
+  check([id10, [id31], [id41, id42, id20]]);
 
   _("Moving 10 in front of 31 in f30 -> update 10, f30");
-  apply(bookmark("10", "f30"));
-  f30.children = ["10", "31"];
+  apply(bookmark(id10, id30));
+  f30.children = [id10, id31];
   apply(f30);
-  check([["10", "31"], ["41", "42", "20"]]);
+  check([[id10, id31], [id41, id42, id20]]);
 
   _("Moving 20 from f40 to f30 -> update 20, f30");
-  apply(bookmark("20", "f30"));
-  f30.children = ["10", "20", "31"];
+  apply(bookmark(id20, id30));
+  f30.children = [id10, id20, id31];
   apply(f30);
-  check([["10", "20", "31"], ["41", "42"]]);
+  check([[id10, id20, id31], [id41, id42]]);
 
   _("Move 20 back to front -> update 20, f30");
-  apply(bookmark("20", ""));
-  f30.children = ["10", "31"];
+  apply(bookmark(id20, ""));
+  f30.children = [id10, id31];
   apply(f30);
-  check([["10", "31"], ["41", "42"], "20"]);
+  check([[id10, id31], [id41, id42], id20]);
 
 }

--- a/services/sync/tests/unit/test_service_attributes.js
+++ b/services/sync/tests/unit/test_service_attributes.js
@@ -79,22 +79,22 @@ function test_syncID() {
   _("Service.syncID is auto-generated, corresponds to preference.");
   new FakeGUIDService();
 
   try {
     // Ensure pristine environment
     do_check_eq(Svc.Prefs.get("client.syncID"), undefined);
 
     // Performing the first get on the attribute will generate a new GUID.
-    do_check_eq(Service.syncID, "fake-guid-0");
-    do_check_eq(Svc.Prefs.get("client.syncID"), "fake-guid-0");
+    do_check_eq(Service.syncID, "fake-guid-00");
+    do_check_eq(Svc.Prefs.get("client.syncID"), "fake-guid-00");
 
     Svc.Prefs.set("client.syncID", Utils.makeGUID());
-    do_check_eq(Svc.Prefs.get("client.syncID"), "fake-guid-1");
-    do_check_eq(Service.syncID, "fake-guid-1");
+    do_check_eq(Svc.Prefs.get("client.syncID"), "fake-guid-01");
+    do_check_eq(Service.syncID, "fake-guid-01");
   } finally {
     Svc.Prefs.resetBranch("");
     new FakeGUIDService();
   }
 }
 
 function test_locked() {
   _("The 'locked' attribute can be toggled with lock() and unlock()");

--- a/services/sync/tests/unit/test_syncengine.js
+++ b/services/sync/tests/unit/test_syncengine.js
@@ -30,22 +30,22 @@ function test_syncID() {
   _("SyncEngine.syncID corresponds to preference");
   let syncTesting = new SyncTestingInfrastructure(server);
   let engine = makeSteamEngine();
   try {
     // Ensure pristine environment
     do_check_eq(Svc.Prefs.get("steam.syncID"), undefined);
 
     // Performing the first get on the attribute will generate a new GUID.
-    do_check_eq(engine.syncID, "fake-guid-0");
-    do_check_eq(Svc.Prefs.get("steam.syncID"), "fake-guid-0");
+    do_check_eq(engine.syncID, "fake-guid-00");
+    do_check_eq(Svc.Prefs.get("steam.syncID"), "fake-guid-00");
 
     Svc.Prefs.set("steam.syncID", Utils.makeGUID());
-    do_check_eq(Svc.Prefs.get("steam.syncID"), "fake-guid-1");
-    do_check_eq(engine.syncID, "fake-guid-1");
+    do_check_eq(Svc.Prefs.get("steam.syncID"), "fake-guid-01");
+    do_check_eq(engine.syncID, "fake-guid-01");
   } finally {
     Svc.Prefs.resetBranch("");
   }
 }
 
 function test_lastSync() {
   _("SyncEngine.lastSync and SyncEngine.lastSyncLocal correspond to preferences");
   let syncTesting = new SyncTestingInfrastructure(server);

--- a/services/sync/tests/unit/test_syncengine_sync.js
+++ b/services/sync/tests/unit/test_syncengine_sync.js
@@ -167,17 +167,17 @@ add_test(function test_syncStartup_syncI
   let global = new ServerWBO('global',
                              {engines: {rotary: {version: engine.version,
                                                 syncID: 'foobar'}}});
   server.registerPathHandler("/1.1/foo/storage/meta/global", global.handler());
 
   try {
 
     // Confirm initial environment
-    do_check_eq(engine.syncID, 'fake-guid-0');
+    do_check_eq(engine.syncID, 'fake-guid-00');
     do_check_eq(engine._tracker.changedIDs["rekolok"], undefined);
 
     engine.lastSync = Date.now() / 1000;
     engine.lastSyncLocal = Date.now();
     engine._syncStartup();
 
     // The engine has assumed the server's syncID
     do_check_eq(engine.syncID, 'foobar');