diff --git a/java/com/google/gerrit/server/git/DefaultChangeReportFormatter.java b/java/com/google/gerrit/server/git/DefaultChangeReportFormatter.java
index 1241585..914f402 100644
--- a/java/com/google/gerrit/server/git/DefaultChangeReportFormatter.java
+++ b/java/com/google/gerrit/server/git/DefaultChangeReportFormatter.java
@@ -26,6 +26,7 @@
   private static final int SUBJECT_MAX_LENGTH = 80;
   private static final String SUBJECT_CROP_APPENDIX = "...";
   private static final int SUBJECT_CROP_RANGE = 10;
+  private static final String NEW_CHANGE_INDICATOR = " [NEW]";
 
   private final UrlFormatter urlFormatter;
 
@@ -36,7 +37,7 @@
 
   @Override
   public String newChange(ChangeReportFormatter.Input input) {
-    return formatChangeUrl(input);
+    return formatChangeUrl(input) + NEW_CHANGE_INDICATOR;
   }
 
   @Override
diff --git a/java/com/google/gerrit/server/git/receive/ReceiveCommits.java b/java/com/google/gerrit/server/git/receive/ReceiveCommits.java
index 02d70b4..39b34df 100644
--- a/java/com/google/gerrit/server/git/receive/ReceiveCommits.java
+++ b/java/com/google/gerrit/server/git/receive/ReceiveCommits.java
@@ -31,7 +31,6 @@
 import static com.google.gerrit.server.git.validators.CommitValidators.NEW_PATCHSET_PATTERN;
 import static com.google.gerrit.server.mail.MailUtil.getRecipientsFromFooters;
 import static java.nio.charset.StandardCharsets.UTF_8;
-import static java.util.Comparator.comparingInt;
 import static java.util.Objects.requireNonNull;
 import static java.util.stream.Collectors.joining;
 import static java.util.stream.Collectors.toList;
@@ -175,14 +174,17 @@
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Objects;
 import java.util.Optional;
 import java.util.Set;
+import java.util.TreeSet;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.Future;
 import java.util.regex.Matcher;
+import java.util.stream.Collectors;
 import java.util.stream.Stream;
 import org.eclipse.jgit.errors.ConfigInvalidException;
 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
@@ -693,15 +695,51 @@
 
   /** Appends messages for successful change creation/updates. */
   private void queueSuccessMessages(List<CreateRequest> newChanges) {
-    List<CreateRequest> created =
-        newChanges.stream().filter(r -> r.change != null).collect(toList());
-    List<ReplaceRequest> updated =
+    // adjacency list for commit => parent
+    Map<String, String> adjList = new HashMap<>();
+    for (CreateRequest cr : newChanges) {
+      String parent = cr.commit.getParentCount() == 0 ? null : cr.commit.getParent(0).name();
+      adjList.put(cr.commit.name(), parent);
+    }
+    for (ReplaceRequest rr : replaceByChange.values()) {
+      String parent = null;
+      if (rr.revCommit != null) {
+        parent = rr.revCommit.getParentCount() == 0 ? null : rr.revCommit.getParent(0).name();
+      }
+      adjList.put(rr.newCommitId.name(), parent);
+    }
+
+    // get commits that are not parents
+    Set<String> leafs = new TreeSet<>(adjList.keySet());
+    leafs.removeAll(adjList.values());
+    // go backwards from the last commit to its parent(s)
+    Set<String> ordered = new LinkedHashSet<>();
+    for (String leaf : leafs) {
+      if (ordered.contains(leaf)) {
+        continue;
+      }
+      while (leaf != null) {
+        if (!ordered.contains(leaf)) {
+          ordered.add(leaf);
+        }
+        leaf = adjList.get(leaf);
+      }
+    }
+    // reverse the order to start with earliest commit
+    List<String> orderedCommits = new ArrayList<>(ordered);
+    Collections.reverse(orderedCommits);
+
+    Map<String, CreateRequest> created =
+        newChanges
+            .stream()
+            .filter(r -> r.change != null)
+            .collect(Collectors.toMap(r -> r.commit.name(), r -> r));
+    Map<String, ReplaceRequest> updated =
         replaceByChange
             .values()
             .stream()
             .filter(r -> r.inputCommand.getResult() == OK)
-            .sorted(comparingInt(r -> r.notes.getChangeId().get()))
-            .collect(toList());
+            .collect(Collectors.toMap(r -> r.newCommitId.name(), r -> r));
 
     if (created.isEmpty() && updated.isEmpty()) {
       return;
@@ -709,63 +747,68 @@
 
     addMessage("");
     addMessage("SUCCESS");
+    addMessage("");
 
-    if (!created.isEmpty()) {
-      addMessage("");
-      addMessage("New Changes:");
-      for (CreateRequest c : created) {
-        addMessage(
-            changeFormatter.newChange(
-                ChangeReportFormatter.Input.builder().setChange(c.change).build()));
-      }
-    }
-
+    boolean edit = false;
+    Boolean isPrivate = null;
+    Boolean wip = null;
     if (!updated.isEmpty()) {
-      addMessage("");
-      addMessage("Updated Changes:");
-      boolean edit = magicBranch != null && (magicBranch.edit || magicBranch.draft);
-      for (ReplaceRequest u : updated) {
-        String subject;
-        Change change = u.notes.getChange();
-        if (edit) {
-          try {
-            subject = receivePack.getRevWalk().parseCommit(u.newCommitId).getShortMessage();
-          } catch (IOException e) {
-            // Log and fall back to original change subject
-            logger.atWarning().withCause(e).log("failed to get subject for edit patch set");
-            subject = change.getSubject();
-          }
-        } else {
-          subject = u.info.getSubject();
+      edit = magicBranch != null && (magicBranch.edit || magicBranch.draft);
+      if (magicBranch != null) {
+        if (magicBranch.isPrivate) {
+          isPrivate = true;
+        } else if (magicBranch.removePrivate) {
+          isPrivate = false;
         }
-
-        boolean isPrivate = change.isPrivate();
-        boolean wip = change.isWorkInProgress();
-        if (magicBranch != null) {
-          if (magicBranch.isPrivate) {
-            isPrivate = true;
-          } else if (magicBranch.removePrivate) {
-            isPrivate = false;
-          }
-          if (magicBranch.workInProgress) {
-            wip = true;
-          } else if (magicBranch.ready) {
-            wip = false;
-          }
+        if (magicBranch.workInProgress) {
+          wip = true;
+        } else if (magicBranch.ready) {
+          wip = false;
         }
-
-        ChangeReportFormatter.Input input =
-            ChangeReportFormatter.Input.builder()
-                .setChange(change)
-                .setSubject(subject)
-                .setIsEdit(edit)
-                .setIsPrivate(isPrivate)
-                .setIsWorkInProgress(wip)
-                .build();
-        addMessage(changeFormatter.changeUpdated(input));
       }
-      addMessage("");
     }
+
+    for (String commit : orderedCommits) {
+      if (created.get(commit) != null) {
+        addCreatedMessage(created.get(commit));
+      } else if (updated.get(commit) != null) {
+        addReplacedMessage(updated.get(commit), edit, isPrivate, wip);
+      }
+    }
+    addMessage("");
+  }
+
+  private void addCreatedMessage(CreateRequest c) {
+    addMessage(
+        changeFormatter.newChange(
+            ChangeReportFormatter.Input.builder().setChange(c.change).build()));
+  }
+
+  private void addReplacedMessage(ReplaceRequest u, boolean edit, Boolean isPrivate, Boolean wip) {
+    String subject;
+    if (edit) {
+      subject =
+          u.revCommit == null ? u.notes.getChange().getSubject() : u.revCommit.getShortMessage();
+    } else {
+      subject = u.info.getSubject();
+    }
+
+    if (isPrivate == null) {
+      isPrivate = u.notes.getChange().isPrivate();
+    }
+    if (wip == null) {
+      wip = u.notes.getChange().isWorkInProgress();
+    }
+
+    ChangeReportFormatter.Input input =
+        ChangeReportFormatter.Input.builder()
+            .setChange(u.notes.getChange())
+            .setSubject(subject)
+            .setIsEdit(edit)
+            .setIsPrivate(isPrivate)
+            .setIsWorkInProgress(wip)
+            .build();
+    addMessage(changeFormatter.changeUpdated(input));
   }
 
   private void insertChangesAndPatchSets(List<CreateRequest> newChanges, Task replaceProgress) {
@@ -2556,6 +2599,7 @@
     final ObjectId newCommitId;
     final ReceiveCommand inputCommand;
     final boolean checkMergedInto;
+    RevCommit revCommit;
     ChangeNotes notes;
     BiMap<RevCommit, PatchSet.Id> revisions;
     PatchSet.Id psId;
@@ -2573,6 +2617,11 @@
       this.inputCommand = requireNonNull(cmd);
       this.checkMergedInto = checkMergedInto;
 
+      try {
+        revCommit = receivePack.getRevWalk().parseCommit(newCommitId);
+      } catch (IOException e) {
+        revCommit = null;
+      }
       revisions = HashBiMap.create();
       for (Ref ref : refs(toChange)) {
         try {
diff --git a/javatests/com/google/gerrit/acceptance/git/AbstractPushForReview.java b/javatests/com/google/gerrit/acceptance/git/AbstractPushForReview.java
index 143a4a4..3e26cab 100644
--- a/javatests/com/google/gerrit/acceptance/git/AbstractPushForReview.java
+++ b/javatests/com/google/gerrit/acceptance/git/AbstractPushForReview.java
@@ -136,6 +136,7 @@
 
   @Inject private RequestScopeOperations requestScopeOperations;
 
+  private static String NEW_CHANGE_INDICATOR = " [NEW]";
   private LabelType patchSetLock;
 
   @BeforeClass
@@ -376,7 +377,7 @@
     r1.assertOkStatus();
     r1.assertChange(Change.Status.NEW, null);
     r1.assertMessage(
-        "New changes:\n  " + url + id1 + " " + r1.getCommit().getShortMessage() + "\n");
+        url + id1 + " " + r1.getCommit().getShortMessage() + NEW_CHANGE_INDICATOR + "\n");
 
     testRepo.reset(initialHead);
     String newMsg = r1.getCommit().getShortMessage() + " v2";
@@ -396,18 +397,17 @@
     r2.assertMessage(
         "success\n"
             + "\n"
-            + "New changes:\n"
-            + "  "
-            + url
-            + id2
-            + " another commit\n"
-            + "\n"
-            + "Updated changes:\n"
             + "  "
             + url
             + id1
             + " "
             + newMsg
+            + "\n"
+            + "  "
+            + url
+            + id2
+            + " another commit"
+            + NEW_CHANGE_INDICATOR
             + "\n");
   }
 
@@ -898,8 +898,7 @@
     assertThat(edit).isPresent();
     EditInfo editInfo = edit.get();
     r.assertMessage(
-        "Updated Changes:\n  "
-            + canonicalWebUrl.get()
+        canonicalWebUrl.get()
             + "c/"
             + project.get()
             + "/+/"
@@ -2412,6 +2411,74 @@
         .contains("warning: " + amended.abbreviate(7).name() + ": no files changed, was rebased");
   }
 
+  @Test
+  public void sequentialCommitMessages() throws Exception {
+    String url = canonicalWebUrl.get() + "c/" + project.get() + "/+/";
+    ObjectId initialHead = testRepo.getRepository().resolve("HEAD");
+
+    PushOneCommit.Result r1 = pushTo("refs/for/master");
+    Change.Id id1 = r1.getChange().getId();
+    r1.assertOkStatus();
+    r1.assertChange(Change.Status.NEW, null);
+    r1.assertMessage(
+        url + id1 + " " + r1.getCommit().getShortMessage() + NEW_CHANGE_INDICATOR + "\n");
+
+    PushOneCommit.Result r2 = pushTo("refs/for/master");
+    Change.Id id2 = r2.getChange().getId();
+    r2.assertOkStatus();
+    r2.assertChange(Change.Status.NEW, null);
+    r2.assertMessage(
+        url + id2 + " " + r2.getCommit().getShortMessage() + NEW_CHANGE_INDICATOR + "\n");
+
+    testRepo.reset(initialHead);
+
+    // rearrange the commit so that change no. 2 is the parent of change no. 1
+    String r1Message = "Position 2";
+    String r2Message = "Position 1";
+    testRepo
+        .branch("HEAD")
+        .commit()
+        .message(r2Message)
+        .insertChangeId(r2.getChangeId().substring(1))
+        .create();
+    testRepo
+        .branch("HEAD")
+        .commit()
+        .message(r1Message)
+        .insertChangeId(r1.getChangeId().substring(1))
+        .create();
+
+    PushOneCommit.Result r3 =
+        pushFactory
+            .create(admin.getIdent(), testRepo, "another commit", "b.txt", "bbb")
+            .to("refs/for/master");
+    Change.Id id3 = r3.getChange().getId();
+    r3.assertOkStatus();
+    r3.assertChange(Change.Status.NEW, null);
+    // should display commit r2, r1, r3 in that order.
+    r3.assertMessage(
+        "success\n"
+            + "\n"
+            + "  "
+            + url
+            + id2
+            + " "
+            + r2Message
+            + "\n"
+            + "  "
+            + url
+            + id1
+            + " "
+            + r1Message
+            + "\n"
+            + "  "
+            + url
+            + id3
+            + " another commit"
+            + NEW_CHANGE_INDICATOR
+            + "\n");
+  }
+
   private DraftInput newDraft(String path, int line, String message) {
     DraftInput d = new DraftInput();
     d.path = path;