--- a/services/sync/modules/engines/extension-storage.js
+++ b/services/sync/modules/engines/extension-storage.js
@@ -134,19 +134,26 @@ class EncryptionRemoteTransformer {
         throw new Error("Record ID is missing or invalid");
       }
 
       let IV = Svc.Crypto.generateRandomIV();
       let ciphertext = Svc.Crypto.encrypt(JSON.stringify(record),
                                           keyBundle.encryptionKeyB64, IV);
       let hmac = ciphertextHMAC(keyBundle, id, IV, ciphertext);
       const encryptedResult = {ciphertext, IV, hmac, id};
+
+      // Copy over the _status field, so that we handle concurrency
+      // headers (If-Match, If-None-Match) correctly.
+      // DON'T copy over "deleted" status, because then we'd leak
+      // plaintext deletes.
+      encryptedResult._status = record._status == "deleted" ? "updated" : record._status;
       if (record.hasOwnProperty("last_modified")) {
         encryptedResult.last_modified = record.last_modified;
       }
+
       return encryptedResult;
     });
   }
 
   decode(record) {
     const self = this;
     return Task.spawn(function* () {
       if (!record.ciphertext) {
@@ -178,16 +185,23 @@ class EncryptionRemoteTransformer {
       if (jsonResult.id != record.id) {
         throw new Error("Record id mismatch: " + jsonResult.id + " != " + record.id);
       }
 
       if (record.hasOwnProperty("last_modified")) {
         jsonResult.last_modified = record.last_modified;
       }
 
+      // _status: deleted records were deleted on a client, but
+      // uploaded as an encrypted blob so we don't leak deletions.
+      // If we get such a record, flag it as deleted.
+      if (jsonResult._status == "deleted") {
+        jsonResult.deleted = true;
+      }
+
       return jsonResult;
     });
   }
 
   /**
    * Retrieve keys to use during encryption.
    *
    * Returns a Promise<KeyBundle>.

--- a/toolkit/components/extensions/test/xpcshell/test_ext_storage_sync.js
+++ b/toolkit/components/extensions/test/xpcshell/test_ext_storage_sync.js
@@ -990,19 +990,20 @@ add_task(function* test_storage_sync_pul
       yield ExtensionStorageSync.syncAll();
       server.clearPosts();
 
       let calls = [];
       yield ExtensionStorageSync.addOnChangedListener(extension, function() {
         calls.push(arguments);
       }, context);
 
-      yield server.addRecord(collectionId, {
+      yield server.encryptAndAddRecord(new CollectionKeyEncryptionRemoteTransformer(extension.id), collectionId, {
         "id": "key-my_2D_key",
-        "deleted": true,
+        "data": 6,
+        "_status": "deleted",
       });
 
       yield ExtensionStorageSync.syncAll();
       const remoteValues = (yield ExtensionStorageSync.get(extension, "my-key", context));
       ok(!remoteValues["my-key"],
          "ExtensionStorageSync.get() shows value was deleted by sync");
 
       equal(server.getPosts().length, 0,
@@ -1056,14 +1057,19 @@ add_task(function* test_storage_sync_pus
       // Doesn't push keys because keys were pushed by a previous test.
       posts = server.getPosts();
       equal(posts.length, 3,
             "deleting a value should trigger another push");
       const post = posts[2];
       assertPostedUpdatedRecord(post, 1000);
       equal(post.path, collectionRecordsPath(collectionId) + "/key-my_2D_key",
             "pushing a deleted value should go to the same path");
-      ok(post.method, "DELETE");
-      ok(!post.body,
-         "deleting a value shouldn't have a body");
+      ok(post.method, "PUT");
+      ok(post.body.data.ciphertext,
+         "deleting a value should have an encrypted body");
+      const decoded = yield new CollectionKeyEncryptionRemoteTransformer(extensionId).decode(post.body.data);
+      equal(decoded._status, "deleted");
+      // Ideally, we'd check that decoded.deleted is not true, because
+      // the encrypted record shouldn't have it, but the decoder will
+      // add it when it sees _status == deleted
     });
   });
 });