diff --git a/src/applications/diffusion/controller/DiffusionCommitController.php b/src/applications/diffusion/controller/DiffusionCommitController.php
--- a/src/applications/diffusion/controller/DiffusionCommitController.php
+++ b/src/applications/diffusion/controller/DiffusionCommitController.php
@@ -129,6 +129,12 @@
           ),
           $message));
 
+      if ($commit->isUnreachable()) {
+        $this->commitErrors[] = pht(
+          'This commit has been deleted in the repository: it is no longer '.
+          'reachable from any branch, tag, or ref.');
+      }
+
       if ($this->getCommitErrors()) {
         $error_panel = id(new PHUIInfoView())
           ->appendChild($this->getCommitErrors())
diff --git a/src/applications/repository/engine/PhabricatorRepositoryDiscoveryEngine.php b/src/applications/repository/engine/PhabricatorRepositoryDiscoveryEngine.php
--- a/src/applications/repository/engine/PhabricatorRepositoryDiscoveryEngine.php
+++ b/src/applications/repository/engine/PhabricatorRepositoryDiscoveryEngine.php
@@ -444,10 +444,17 @@
       return;
     }
 
+    // When filling the cache we ignore commits which have been marked as
+    // unreachable, treating them as though they do not exist. When recording
+    // commits later we'll revive commits that exist but are unreachable.
+
     $commits = id(new PhabricatorRepositoryCommit())->loadAllWhere(
-      'repositoryID = %d AND commitIdentifier IN (%Ls)',
+      'repositoryID = %d AND commitIdentifier IN (%Ls)
+        AND (importStatus & %d) != %d',
       $this->getRepository()->getID(),
-      $identifiers);
+      $identifiers,
+      PhabricatorRepositoryCommit::IMPORTED_UNREACHABLE,
+      PhabricatorRepositoryCommit::IMPORTED_UNREACHABLE);
 
     foreach ($commits as $commit) {
       $this->commitCache[$commit->getCommitIdentifier()] = true;
@@ -493,6 +500,24 @@
     array $parents) {
 
     $commit = new PhabricatorRepositoryCommit();
+    $conn_w = $repository->establishConnection('w');
+
+    // First, try to revive an existing unreachable commit (if one exists) by
+    // removing the "unreachable" flag. If we succeed, we don't need to do
+    // anything else: we already discovered this commit some time ago.
+    queryfx(
+      $conn_w,
+      'UPDATE %T SET importStatus = (importStatus & ~%d)
+        WHERE repositoryID = %d AND commitIdentifier = %s',
+      $commit->getTableName(),
+      PhabricatorRepositoryCommit::IMPORTED_UNREACHABLE,
+      $repository->getID(),
+      $commit_identifier);
+    if ($conn_w->getAffectedRows()) {
+      return;
+    }
+
+
     $commit->setRepositoryID($repository->getID());
     $commit->setCommitIdentifier($commit_identifier);
     $commit->setEpoch($epoch);
@@ -502,10 +527,7 @@
 
     $data = new PhabricatorRepositoryCommitData();
 
-    $conn_w = $repository->establishConnection('w');
-
     try {
-
       // If this commit has parents, look up their IDs. The parent commits
       // should always exist already.
 
@@ -583,8 +605,6 @@
             'commit'      => $commit,
           )));
 
-
-
     } catch (AphrontDuplicateKeyQueryException $ex) {
       $commit->killTransaction();
       // Ignore. This can happen because we discover the same new commit
diff --git a/src/applications/repository/storage/PhabricatorRepositoryCommit.php b/src/applications/repository/storage/PhabricatorRepositoryCommit.php
--- a/src/applications/repository/storage/PhabricatorRepositoryCommit.php
+++ b/src/applications/repository/storage/PhabricatorRepositoryCommit.php
@@ -32,6 +32,7 @@
   const IMPORTED_ALL = 15;
 
   const IMPORTED_CLOSEABLE = 1024;
+  const IMPORTED_UNREACHABLE = 2048;
 
   private $commitData = self::ATTACHABLE;
   private $audits = self::ATTACHABLE;
@@ -58,6 +59,10 @@
     return $this->isPartiallyImported(self::IMPORTED_ALL);
   }
 
+  public function isUnreachable() {
+    return $this->isPartiallyImported(self::IMPORTED_UNREACHABLE);
+  }
+
   public function writeImportStatusFlag($flag) {
     queryfx(
       $this->establishConnection('w'),