diff --git a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/rest/change/DeleteDraftPatchSetIT.java b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/rest/change/DeleteDraftPatchSetIT.java
index cda2c31..cc66394 100644
--- a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/rest/change/DeleteDraftPatchSetIT.java
+++ b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/rest/change/DeleteDraftPatchSetIT.java
@@ -16,18 +16,24 @@
 
 import static com.google.common.truth.Truth.assertThat;
 
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
 import com.google.gerrit.acceptance.AbstractDaemonTest;
+import com.google.gerrit.acceptance.NoHttpd;
 import com.google.gerrit.acceptance.PushOneCommit;
 import com.google.gerrit.acceptance.PushOneCommit.Result;
-import com.google.gerrit.acceptance.RestResponse;
-import com.google.gerrit.acceptance.RestSession;
 import com.google.gerrit.acceptance.TestAccount;
 import com.google.gerrit.extensions.api.changes.DraftInput;
+import com.google.gerrit.extensions.api.changes.ReviewInput;
+import com.google.gerrit.extensions.api.changes.ReviewInput.CommentInput;
 import com.google.gerrit.extensions.client.ChangeStatus;
+import com.google.gerrit.extensions.client.Side;
 import com.google.gerrit.extensions.common.ChangeInfo;
+import com.google.gerrit.extensions.restapi.ResourceConflictException;
 import com.google.gerrit.extensions.restapi.ResourceNotFoundException;
 import com.google.gerrit.reviewdb.client.Change;
+import com.google.gerrit.reviewdb.client.ChangeMessage;
+import com.google.gerrit.reviewdb.client.PatchLineComment;
 import com.google.gerrit.reviewdb.client.PatchSet;
 import com.google.gerrit.reviewdb.client.RefNames;
 import com.google.gerrit.server.config.AllUsersName;
@@ -38,6 +44,9 @@
 import org.eclipse.jgit.lib.Repository;
 import org.junit.Test;
 
+import java.util.HashMap;
+
+@NoHttpd
 public class DeleteDraftPatchSetIT extends AbstractDaemonTest {
 
   @Inject
@@ -51,9 +60,11 @@
     ChangeInfo c = get(triplet);
     assertThat(c.id).isEqualTo(triplet);
     assertThat(c.status).isEqualTo(ChangeStatus.NEW);
-    RestResponse r = deletePatchSet(changeId, ps, adminRestSession);
-    assertThat(r.getEntityContent()).isEqualTo("Patch set is not a draft");
-    r.assertConflict();
+
+    exception.expect(ResourceConflictException.class);
+    exception.expectMessage("Patch set is not a draft");
+    setApiUser(admin);
+    deletePatchSet(changeId, ps);
   }
 
   @Test
@@ -64,9 +75,11 @@
     ChangeInfo c = get(triplet);
     assertThat(c.id).isEqualTo(triplet);
     assertThat(c.status).isEqualTo(ChangeStatus.DRAFT);
-    RestResponse r = deletePatchSet(changeId, ps, userRestSession);
-    assertThat(r.getEntityContent()).isEqualTo("Not found: " + changeId);
-    r.assertNotFound();
+
+    exception.expect(ResourceNotFoundException.class);
+    exception.expectMessage("Not found: " + changeId);
+    setApiUser(user);
+    deletePatchSet(changeId, ps);
   }
 
   @Test
@@ -87,14 +100,14 @@
     assertThat(cd.patchSets()).hasSize(2);
     assertThat(cd.change().currentPatchSetId().get()).isEqualTo(2);
     assertThat(cd.change().getStatus()).isEqualTo(Change.Status.DRAFT);
-    deletePatchSet(changeId, ps, adminRestSession).assertNoContent();
+    deletePatchSet(changeId, ps);
 
     cd = getChange(changeId);
     assertThat(cd.patchSets()).hasSize(1);
     assertThat(cd.change().currentPatchSetId().get()).isEqualTo(1);
 
     ps = getCurrentPatchSet(changeId);
-    deletePatchSet(changeId, ps, adminRestSession).assertNoContent();
+    deletePatchSet(changeId, ps);
     assertThat(queryProvider.get().byKeyPrefix(changeId)).isEmpty();
 
     if (notesMigration.writeChanges()) {
@@ -105,6 +118,76 @@
     gApi.changes().id(ps.getId().getParentKey().get());
   }
 
+  @Test
+  public void deleteDraftPS1() throws Exception {
+    String changeId = createDraftChangeWith2PS();
+
+    ReviewInput rin = new ReviewInput();
+    rin.message = "Change message";
+    CommentInput cin = new CommentInput();
+    cin.line = 1;
+    cin.patchSet = 1;
+    cin.path = PushOneCommit.FILE_NAME;
+    cin.side = Side.REVISION;
+    cin.message = "Inline comment";
+    rin.comments = new HashMap<>();
+    rin.comments.put(cin.path, ImmutableList.of(cin));
+    gApi.changes().id(changeId).revision(1).review(rin);
+
+    ChangeData cd = getChange(changeId);
+    PatchSet.Id delPsId = new PatchSet.Id(cd.getId(), 1);
+    PatchSet ps = cd.patchSet(delPsId);
+    deletePatchSet(changeId, ps);
+
+    cd = getChange(changeId);
+    assertThat(cd.patchSets()).hasSize(1);
+    assertThat(Iterables.getOnlyElement(cd.patchSets()).getId().get())
+        .isEqualTo(2);
+
+    // Other entities based on deleted patch sets are also deleted.
+    for (ChangeMessage m : cd.messages()) {
+      assertThat(m.getPatchSetId()).named(m.toString()).isNotEqualTo(delPsId);
+    }
+    for (PatchLineComment c : cd.publishedComments()) {
+      assertThat(c.getPatchSetId()).named(c.toString()).isNotEqualTo(delPsId);
+    }
+  }
+
+  @Test
+  public void deleteDraftPS2() throws Exception {
+    String changeId = createDraftChangeWith2PS();
+
+    ReviewInput rin = new ReviewInput();
+    rin.message = "Change message";
+    CommentInput cin = new CommentInput();
+    cin.line = 1;
+    cin.patchSet = 1;
+    cin.path = PushOneCommit.FILE_NAME;
+    cin.side = Side.REVISION;
+    cin.message = "Inline comment";
+    rin.comments = new HashMap<>();
+    rin.comments.put(cin.path, ImmutableList.of(cin));
+    gApi.changes().id(changeId).revision(1).review(rin);
+
+    ChangeData cd = getChange(changeId);
+    PatchSet.Id delPsId = new PatchSet.Id(cd.getId(), 2);
+    PatchSet ps = cd.patchSet(delPsId);
+    deletePatchSet(changeId, ps);
+
+    cd = getChange(changeId);
+    assertThat(cd.patchSets()).hasSize(1);
+    assertThat(Iterables.getOnlyElement(cd.patchSets()).getId().get())
+        .isEqualTo(1);
+
+    // Other entities based on deleted patch sets are also deleted.
+    for (ChangeMessage m : cd.messages()) {
+      assertThat(m.getPatchSetId()).named(m.toString()).isNotEqualTo(delPsId);
+    }
+    for (PatchLineComment c : cd.publishedComments()) {
+      assertThat(c.getPatchSetId()).named(c.toString()).isNotEqualTo(delPsId);
+    }
+  }
+
   private Ref getDraftRef(TestAccount account, Change.Id changeId)
       throws Exception {
     try (Repository repo = repoManager.openRepository(allUsers)) {
@@ -128,11 +211,7 @@
     return Iterables.getOnlyElement(queryProvider.get().byKeyPrefix(changeId));
   }
 
-  private static RestResponse deletePatchSet(String changeId,
-      PatchSet ps, RestSession s) throws Exception {
-    return s.delete("/changes/"
-        + changeId
-        + "/revisions/"
-        + ps.getRevision().get());
+  private void deletePatchSet(String changeId, PatchSet ps) throws Exception {
+    gApi.changes().id(changeId).revision(ps.getId().get()).delete();
   }
 }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/notedb/ChangeRebuilderImpl.java b/gerrit-server/src/main/java/com/google/gerrit/server/notedb/ChangeRebuilderImpl.java
index a3a58a3..53269b2 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/notedb/ChangeRebuilderImpl.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/notedb/ChangeRebuilderImpl.java
@@ -14,6 +14,7 @@
 
 package com.google.gerrit.server.notedb;
 
+import static com.google.common.base.MoreObjects.firstNonNull;
 import static com.google.common.base.Preconditions.checkArgument;
 import static com.google.common.base.Preconditions.checkNotNull;
 import static com.google.common.base.Preconditions.checkState;
@@ -239,8 +240,16 @@
     // Delete ref only after hashtags have been read
     deleteRef(change, changeMetaRepo, manager.getChangeRepo().cmds);
 
+    Integer minPsNum = null;
     for (PatchSet ps : bundle.getPatchSets()) {
-      events.add(new PatchSetEvent(change, ps, manager.getChangeRepo().rw));
+      int n = ps.getId().get();
+      if (minPsNum == null || n < minPsNum) {
+        minPsNum = n;
+      }
+    }
+    for (PatchSet ps : bundle.getPatchSets()) {
+      events.add(new PatchSetEvent(
+          change, ps, checkNotNull(minPsNum), manager.getChangeRepo().rw));
       for (PatchLineComment c : getPatchLineComments(bundle, ps)) {
         PatchLineCommentEvent e =
             new PatchLineCommentEvent(c, change, ps, patchListCache);
@@ -262,7 +271,7 @@
           new ChangeMessageEvent(msg, noteDbChange, change.getCreatedOn()));
     }
 
-    sortEvents(change.getId(), events);
+    sortEvents(change.getId(), events, minPsNum);
 
     events.add(new FinalUpdatesEvent(change, noteDbChange));
 
@@ -301,13 +310,21 @@
         }).toSortedList(PatchLineCommentsUtil.PLC_ORDER);
   }
 
-  private void sortEvents(Change.Id changeId, List<Event> events) {
+  private void sortEvents(Change.Id changeId, List<Event> events,
+      Integer minPsNum) {
     Collections.sort(events, EVENT_ORDER);
 
     // Fill in any missing patch set IDs using the latest patch set of the
-    // change at the time of the event. This is as if a user added a
+    // change at the time of the event, because NoteDb can't represent actions
+    // with no associated patch set ID. This workaround is as if a user added a
     // ChangeMessage on the change by replying from the latest patch set.
-    int ps = 1;
+    //
+    // Start with the first patch set that actually exists. If there are no
+    // patch sets at all, minPsNum will be null, so just bail and use 1 as the
+    // patch set ID. The corresponding patch set won't exist, but this change is
+    // probably corrupt anyway, as deleting the last draft patch set should have
+    // deleted the whole change.
+    int ps = firstNonNull(minPsNum, 1);
     for (Event e : events) {
       if (e.psId == null) {
         e.psId = new PatchSet.Id(changeId, ps);
@@ -613,14 +630,16 @@
   private static class PatchSetEvent extends Event {
     private final Change change;
     private final PatchSet ps;
+    private final boolean createChange;
     private final RevWalk rw;
 
-    PatchSetEvent(Change change, PatchSet ps, RevWalk rw) {
+    PatchSetEvent(Change change, PatchSet ps, int minPsNum, RevWalk rw) {
       super(ps.getId(), ps.getUploader(), ps.getCreatedOn(),
           change.getCreatedOn(), null);
       this.change = change;
       this.ps = ps;
       this.rw = rw;
+      this.createChange = ps.getPatchSetId() == minPsNum;
     }
 
     @Override
@@ -632,7 +651,7 @@
     void apply(ChangeUpdate update) throws IOException, OrmException {
       checkUpdate(update);
       update.setSubject(change.getSubject());
-      if (ps.getPatchSetId() == 1) {
+      if (createChange) {
         update.setSubjectForCommit("Create change");
         update.setChangeId(change.getKey().get());
         update.setBranch(change.getDest().get());