--- a/browser/extensions/formautofill/ProfileStorage.jsm
+++ b/browser/extensions/formautofill/ProfileStorage.jsm
@@ -1111,16 +1111,20 @@ class AutofillRecords {
     return this.data.findIndex(record => {
       return record.guid == guid && (!record.deleted || includeDeleted);
     });
   }
 
   _migrateRecord(record) {
     let hasChanges = false;
 
+    if (record.deleted) {
+      return hasChanges;
+    }
+
     if (!record.version || isNaN(record.version) || record.version < 1) {
       this.log.warn("Invalid record version:", record.version);
 
       // Force to run the migration.
       record.version = 0;
     }
 
     if (record.version < this.version) {
@@ -1191,16 +1195,20 @@ class Addresses extends AutofillRecords 
 
   _computeFields(address) {
     // NOTE: Remember to bump the schema version number if any of the existing
     //       computing algorithm changes. (No need to bump when just adding new
     //       computed fields)
 
     let hasNewComputedFields = false;
 
+    if (address.deleted) {
+      return hasNewComputedFields;
+    }
+
     // Compute name
     if (!("name" in address)) {
       let name = FormAutofillNameUtils.joinNameParts({
         given: address["given-name"],
         middle: address["additional-name"],
         family: address["family-name"],
       });
       address.name = name;
@@ -1454,16 +1462,20 @@ class CreditCards extends AutofillRecord
 
   _computeFields(creditCard) {
     // NOTE: Remember to bump the schema version number if any of the existing
     //       computing algorithm changes. (No need to bump when just adding new
     //       computed fields)
 
     let hasNewComputedFields = false;
 
+    if (creditCard.deleted) {
+      return hasNewComputedFields;
+    }
+
     // Compute split names
     if (!("cc-given-name" in creditCard)) {
       let nameParts = FormAutofillNameUtils.splitName(creditCard["cc-name"]);
       creditCard["cc-given-name"] = nameParts.given;
       creditCard["cc-additional-name"] = nameParts.middle;
       creditCard["cc-family-name"] = nameParts.family;
       hasNewComputedFields = true;
     }

--- a/browser/extensions/formautofill/test/unit/test_migrateRecords.js
+++ b/browser/extensions/formautofill/test/unit/test_migrateRecords.js
@@ -96,16 +96,33 @@ const ADDRESS_TESTCASES = [
     },
     expectedResult: {
       guid: "test-guid",
       version: ADDRESS_SCHEMA_VERSION,
       "given-name": "Timothy",
       name: "Timothy",
     },
   },
+  {
+    description: "The migration shouldn't be invoked on tombstones.",
+    record: {
+      guid: "test-guid",
+      timeLastModified: 12345,
+      deleted: true,
+    },
+    expectedResult: {
+      guid: "test-guid",
+      timeLastModified: 12345,
+      deleted: true,
+
+      // Make sure no new fields are appended.
+      version: undefined,
+      name: undefined,
+    },
+  },
 ];
 
 const CREDIT_CARD_TESTCASES = [
   {
     description: "The record version is equal to the current version. The migration shouldn't be invoked.",
     record: {
       guid: "test-guid",
       version: CREDIT_CARD_SCHEMA_VERSION,
@@ -189,16 +206,33 @@ const CREDIT_CARD_TESTCASES = [
     },
     expectedResult: {
       guid: "test-guid",
       version: CREDIT_CARD_SCHEMA_VERSION,
       "cc-name": "Timothy",
       "cc-given-name": "Timothy",
     },
   },
+  {
+    description: "The migration shouldn't be invoked on tombstones.",
+    record: {
+      guid: "test-guid",
+      timeLastModified: 12345,
+      deleted: true,
+    },
+    expectedResult: {
+      guid: "test-guid",
+      timeLastModified: 12345,
+      deleted: true,
+
+      // Make sure no new fields are appended.
+      version: undefined,
+      "cc-given-name": undefined,
+    },
+  },
 ];
 
 let do_check_record_matches = (expectedRecord, record) => {
   for (let key in expectedRecord) {
     do_check_eq(expectedRecord[key], record[key]);
   }
 };