diff --git a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/notedb/ChangeRebuilderIT.java b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/notedb/ChangeRebuilderIT.java
index ed38d02..b443e66 100644
--- a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/notedb/ChangeRebuilderIT.java
+++ b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/server/notedb/ChangeRebuilderIT.java
@@ -59,6 +59,7 @@
 import com.google.gerrit.server.git.UpdateException;
 import com.google.gerrit.server.notedb.ChangeBundle;
 import com.google.gerrit.server.notedb.ChangeNotes;
+import com.google.gerrit.server.notedb.ChangeRebuilder.NoPatchSetsException;
 import com.google.gerrit.server.notedb.NoteDbChangeState;
 import com.google.gerrit.server.notedb.NoteDbUpdateManager;
 import com.google.gerrit.server.notedb.TestChangeRebuilderWrapper;
@@ -954,6 +955,22 @@
     assertChangeUpToDate(false, id);
   }
 
+  @Test
+  public void rebuildChangeWithNoPatchSets() throws Exception {
+    PushOneCommit.Result r = createChange();
+    Change.Id id = r.getPatchSetId().getParentKey();
+    db.changes().beginTransaction(id);
+    try {
+      db.patchSets().delete(db.patchSets().byChange(id));
+      db.commit();
+    } finally {
+      db.rollback();
+    }
+
+    exception.expect(NoPatchSetsException.class);
+    checker.rebuildAndCheckChanges(id);
+  }
+
   private void assertChangesReadOnly(RestApiException e) throws Exception {
     Throwable cause = e.getCause();
     assertThat(cause).isInstanceOf(UpdateException.class);
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/notedb/ChangeRebuilder.java b/gerrit-server/src/main/java/com/google/gerrit/server/notedb/ChangeRebuilder.java
index ee64376..679b5e2 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/notedb/ChangeRebuilder.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/notedb/ChangeRebuilder.java
@@ -32,6 +32,15 @@
 import java.util.concurrent.Callable;
 
 public abstract class ChangeRebuilder {
+  public static class NoPatchSetsException extends OrmException {
+    private static final long serialVersionUID = 1L;
+
+    NoPatchSetsException(Change.Id changeId) {
+      super("Change " + changeId
+          + " cannot be rebuilt because it has no patch sets");
+    }
+  }
+
   private final SchemaFactory<ReviewDb> schemaFactory;
 
   protected ChangeRebuilder(SchemaFactory<ReviewDb> schemaFactory) {
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 8244628..08acbad 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
@@ -287,6 +287,8 @@
       for (Change.Id changeId : allChanges.get(project)) {
         try {
           buildUpdates(manager, ChangeBundle.fromReviewDb(db, changeId));
+        } catch (NoPatchSetsException e) {
+          log.warn(e.getMessage());
         } catch (Throwable t) {
           log.error("Failed to rebuild change " + changeId, t);
           ok = false;
@@ -304,6 +306,10 @@
       throws IOException, OrmException {
     manager.setCheckExpectedState(false);
     Change change = new Change(bundle.getChange());
+    if (bundle.getPatchSets().isEmpty()) {
+      throw new NoPatchSetsException(change.getId());
+    }
+
     PatchSet.Id currPsId = change.currentPatchSetId();
     // We will rebuild all events, except for draft comments, in buckets based
     // on author and timestamp.