diff --git a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/mail/AbstractMailIT.java b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/mail/AbstractMailIT.java
index 4c38d83..d6ad269 100644
--- a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/mail/AbstractMailIT.java
+++ b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/mail/AbstractMailIT.java
@@ -132,9 +132,9 @@
         + "> \n";
   }
 
-  protected static String textFooterForChange(String changeId, String timestamp) {
-    return "Gerrit-Change-Id: "
-        + changeId
+  protected static String textFooterForChange(int changeNumber, String timestamp) {
+    return "Gerrit-Change-Number: "
+        + changeNumber
         + "\n"
         + "Gerrit-PatchSet: 1\n"
         + "Gerrit-MessageType: comment\n"
diff --git a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/mail/ListMailFilterIT.java b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/mail/ListMailFilterIT.java
index 1dcdd97..a96c6ec 100644
--- a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/mail/ListMailFilterIT.java
+++ b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/mail/ListMailFilterIT.java
@@ -113,7 +113,7 @@
             null,
             null,
             null);
-    b.textContent(txt + textFooterForChange(changeId, ts));
+    b.textContent(txt + textFooterForChange(changeInfo._number, ts));
 
     mailProcessor.process(b.build());
     return changeInfo;
diff --git a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/mail/MailMetadataIT.java b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/mail/MailMetadataIT.java
index ada222a..7cef8e7 100644
--- a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/mail/MailMetadataIT.java
+++ b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/mail/MailMetadataIT.java
@@ -67,7 +67,8 @@
 
     Map<String, Object> expectedHeaders = new HashMap<>();
     expectedHeaders.put("Gerrit-PatchSet", "1");
-    expectedHeaders.put("Gerrit-Change-Id", newChange.getChangeId());
+    expectedHeaders.put(
+        "Gerrit-Change-Number", String.valueOf(newChange.getChange().getId().get()));
     expectedHeaders.put("Gerrit-MessageType", "newchange");
     expectedHeaders.put("Gerrit-Commit", newChange.getCommit().getId().name());
     expectedHeaders.put("Gerrit-ChangeURL", changeURL);
@@ -102,7 +103,8 @@
     String changeURL = "<" + canonicalWebUrl.get() + newChange.getChange().getId().get() + ">";
     Map<String, Object> expectedHeaders = new HashMap<>();
     expectedHeaders.put("Gerrit-PatchSet", "1");
-    expectedHeaders.put("Gerrit-Change-Id", newChange.getChangeId());
+    expectedHeaders.put(
+        "Gerrit-Change-Number", String.valueOf(newChange.getChange().getId().get()));
     expectedHeaders.put("Gerrit-MessageType", "comment");
     expectedHeaders.put("Gerrit-Commit", newChange.getCommit().getId().name());
     expectedHeaders.put("Gerrit-ChangeURL", changeURL);
diff --git a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/mail/MailProcessorIT.java b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/mail/MailProcessorIT.java
index e7a0cda..9de4797 100644
--- a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/mail/MailProcessorIT.java
+++ b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/mail/MailProcessorIT.java
@@ -51,7 +51,7 @@
             null,
             null,
             null);
-    b.textContent(txt + textFooterForChange(changeId, ts));
+    b.textContent(txt + textFooterForChange(changeInfo._number, ts));
 
     mailProcessor.process(b.build());
 
@@ -79,7 +79,7 @@
             "Some Inline Comment",
             null,
             null);
-    b.textContent(txt + textFooterForChange(changeId, ts));
+    b.textContent(txt + textFooterForChange(changeInfo._number, ts));
 
     mailProcessor.process(b.build());
 
@@ -115,7 +115,7 @@
             null,
             "Some Comment on File 1",
             null);
-    b.textContent(txt + textFooterForChange(changeId, ts));
+    b.textContent(txt + textFooterForChange(changeInfo._number, ts));
 
     mailProcessor.process(b.build());
 
@@ -152,7 +152,7 @@
             "Some Inline Comment",
             null,
             null);
-    b.textContent(txt + textFooterForChange(changeId, ts));
+    b.textContent(txt + textFooterForChange(changeInfo._number, ts));
 
     mailProcessor.process(b.build());
     comments = gApi.changes().id(changeId).current().commentsAsList();
@@ -183,7 +183,7 @@
             "Some Inline Comment",
             null,
             null);
-    b.textContent(txt + textFooterForChange(changeId, ts));
+    b.textContent(txt + textFooterForChange(changeInfo._number, ts));
 
     // Set account state to inactive
     gApi.accounts().id("user").setActive(false);
@@ -219,7 +219,7 @@
     MailMessage.Builder b =
         messageBuilderWithDefaultFields()
             .from(user.emailAddress)
-            .textContent(txt + textFooterForChange(changeId, ts));
+            .textContent(txt + textFooterForChange(changeInfo._number, ts));
 
     sender.clear();
     mailProcessor.process(b.build());
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/mail/MetadataName.java b/gerrit-server/src/main/java/com/google/gerrit/server/mail/MetadataName.java
index 3db55c0..3080e4f 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/mail/MetadataName.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/mail/MetadataName.java
@@ -15,7 +15,7 @@
 package com.google.gerrit.server.mail;
 
 public final class MetadataName {
-  public static final String CHANGE_ID = "Gerrit-Change-Id";
+  public static final String CHANGE_NUMBER = "Gerrit-Change-Number";
   public static final String PATCH_SET = "Gerrit-PatchSet";
   public static final String MESSAGE_TYPE = "Gerrit-MessageType";
   public static final String TIMESTAMP = "Gerrit-Comment-Date";
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/mail/receive/MailMetadata.java b/gerrit-server/src/main/java/com/google/gerrit/server/mail/receive/MailMetadata.java
index f85291c..04c2add 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/mail/receive/MailMetadata.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/mail/receive/MailMetadata.java
@@ -19,14 +19,14 @@
 
 /** MailMetadata represents metadata parsed from inbound email. */
 public class MailMetadata {
-  public String changeId;
+  public Integer changeNumber;
   public Integer patchSet;
   public String author; // Author of the email
   public Timestamp timestamp;
   public String messageType; // we expect comment here
 
   public boolean hasRequiredFields() {
-    return changeId != null
+    return changeNumber != null
         && patchSet != null
         && author != null
         && timestamp != null
@@ -36,7 +36,7 @@
   @Override
   public String toString() {
     return MoreObjects.toStringHelper(this)
-        .add("Change-Id", changeId)
+        .add("Change-Number", changeNumber)
         .add("Patch-Set", patchSet)
         .add("Author", author)
         .add("Timestamp", timestamp)
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/mail/receive/MailProcessor.java b/gerrit-server/src/main/java/com/google/gerrit/server/mail/receive/MailProcessor.java
index 862da9f..accf7ba 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/mail/receive/MailProcessor.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/mail/receive/MailProcessor.java
@@ -160,12 +160,12 @@
 
     try (ManualRequestContext ctx = oneOffRequestContext.openAs(account)) {
       List<ChangeData> changeDataList =
-          queryProvider.get().byKey(Change.Key.parse(metadata.changeId));
+          queryProvider.get().byLegacyChangeId(new Change.Id(metadata.changeNumber));
       if (changeDataList.size() != 1) {
         log.error(
             String.format(
                 "Message %s references unique change %s, but there are %d matching changes in the index. Will delete message.",
-                message.id(), metadata.changeId, changeDataList.size()));
+                message.id(), metadata.changeNumber, changeDataList.size()));
         return;
       }
       ChangeData cd = changeDataList.get(0);
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/mail/receive/MetadataParser.java b/gerrit-server/src/main/java/com/google/gerrit/server/mail/receive/MetadataParser.java
index a18da68..7085051 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/mail/receive/MetadataParser.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/mail/receive/MetadataParser.java
@@ -38,9 +38,9 @@
 
     // Check email headers for X-Gerrit-<Name>
     for (String header : m.additionalHeaders()) {
-      if (header.startsWith(toHeaderWithDelimiter(MetadataName.CHANGE_ID))) {
-        metadata.changeId =
-            header.substring(toHeaderWithDelimiter(MetadataName.CHANGE_ID).length());
+      if (header.startsWith(toHeaderWithDelimiter(MetadataName.CHANGE_NUMBER))) {
+        String num = header.substring(toHeaderWithDelimiter(MetadataName.CHANGE_NUMBER).length());
+        metadata.changeNumber = Ints.tryParse(num);
       } else if (header.startsWith(toHeaderWithDelimiter(MetadataName.PATCH_SET))) {
         String ps = header.substring(toHeaderWithDelimiter(MetadataName.PATCH_SET).length());
         metadata.patchSet = Ints.tryParse(ps);
@@ -84,8 +84,9 @@
 
   private static void extractFooters(String[] lines, MailMetadata metadata, MailMessage m) {
     for (String line : lines) {
-      if (metadata.changeId == null && line.contains(MetadataName.CHANGE_ID)) {
-        metadata.changeId = extractFooter(toFooterWithDelimiter(MetadataName.CHANGE_ID), line);
+      if (metadata.changeNumber == null && line.contains(MetadataName.CHANGE_NUMBER)) {
+        metadata.changeNumber =
+            Ints.tryParse(extractFooter(toFooterWithDelimiter(MetadataName.CHANGE_NUMBER), line));
       } else if (metadata.patchSet == null && line.contains(MetadataName.PATCH_SET)) {
         metadata.patchSet =
             Ints.tryParse(extractFooter(toFooterWithDelimiter(MetadataName.PATCH_SET), line));
diff --git a/gerrit-server/src/test/java/com/google/gerrit/server/mail/receive/MetadataParserTest.java b/gerrit-server/src/test/java/com/google/gerrit/server/mail/receive/MetadataParserTest.java
index 0c4507e..84bae96 100644
--- a/gerrit-server/src/test/java/com/google/gerrit/server/mail/receive/MetadataParserTest.java
+++ b/gerrit-server/src/test/java/com/google/gerrit/server/mail/receive/MetadataParserTest.java
@@ -34,7 +34,7 @@
     b.dateReceived(new DateTime());
     b.subject("");
 
-    b.addAdditionalHeader(toHeaderWithDelimiter(MetadataName.CHANGE_ID) + "cid");
+    b.addAdditionalHeader(toHeaderWithDelimiter(MetadataName.CHANGE_NUMBER) + "123");
     b.addAdditionalHeader(toHeaderWithDelimiter(MetadataName.PATCH_SET) + "1");
     b.addAdditionalHeader(toHeaderWithDelimiter(MetadataName.MESSAGE_TYPE) + "comment");
     b.addAdditionalHeader(
@@ -45,7 +45,7 @@
 
     MailMetadata meta = MetadataParser.parse(b.build());
     assertThat(meta.author).isEqualTo(author.getEmail());
-    assertThat(meta.changeId).isEqualTo("cid");
+    assertThat(meta.changeNumber).isEqualTo(123);
     assertThat(meta.patchSet).isEqualTo(1);
     assertThat(meta.messageType).isEqualTo("comment");
     assertThat(meta.timestamp.getTime())
@@ -62,7 +62,7 @@
     b.subject("");
 
     StringBuilder stringBuilder = new StringBuilder();
-    stringBuilder.append(toFooterWithDelimiter(MetadataName.CHANGE_ID) + "cid\r\n");
+    stringBuilder.append(toFooterWithDelimiter(MetadataName.CHANGE_NUMBER) + "123\r\n");
     stringBuilder.append("> " + toFooterWithDelimiter(MetadataName.PATCH_SET) + "1\n");
     stringBuilder.append(toFooterWithDelimiter(MetadataName.MESSAGE_TYPE) + "comment\n");
     stringBuilder.append(
@@ -74,7 +74,7 @@
 
     MailMetadata meta = MetadataParser.parse(b.build());
     assertThat(meta.author).isEqualTo(author.getEmail());
-    assertThat(meta.changeId).isEqualTo("cid");
+    assertThat(meta.changeNumber).isEqualTo(123);
     assertThat(meta.patchSet).isEqualTo(1);
     assertThat(meta.messageType).isEqualTo("comment");
     assertThat(meta.timestamp.getTime())
@@ -92,7 +92,7 @@
 
     StringBuilder stringBuilder = new StringBuilder();
     stringBuilder.append(
-        "<div id\"someid\">" + toFooterWithDelimiter(MetadataName.CHANGE_ID) + "cid</div>");
+        "<div id\"someid\">" + toFooterWithDelimiter(MetadataName.CHANGE_NUMBER) + "123</div>");
     stringBuilder.append("<div>" + toFooterWithDelimiter(MetadataName.PATCH_SET) + "1</div>");
     stringBuilder.append(
         "<div>" + toFooterWithDelimiter(MetadataName.MESSAGE_TYPE) + "comment</div>");
@@ -108,7 +108,7 @@
 
     MailMetadata meta = MetadataParser.parse(b.build());
     assertThat(meta.author).isEqualTo(author.getEmail());
-    assertThat(meta.changeId).isEqualTo("cid");
+    assertThat(meta.changeNumber).isEqualTo(123);
     assertThat(meta.patchSet).isEqualTo(1);
     assertThat(meta.messageType).isEqualTo("comment");
     assertThat(meta.timestamp.getTime())