diff --git a/resources/sql/autopatches/20170418.files.isDeleted.sql b/resources/sql/autopatches/20170418.files.isDeleted.sql
new file mode 100644
--- /dev/null
+++ b/resources/sql/autopatches/20170418.files.isDeleted.sql
@@ -0,0 +1,2 @@
+ALTER TABLE {$NAMESPACE}_file.file
+  ADD isDeleted BOOL NOT NULL DEFAULT 0;
diff --git a/src/__phutil_library_map__.php b/src/__phutil_library_map__.php
--- a/src/__phutil_library_map__.php
+++ b/src/__phutil_library_map__.php
@@ -1098,6 +1098,7 @@
     'FileAllocateConduitAPIMethod' => 'applications/files/conduit/FileAllocateConduitAPIMethod.php',
     'FileConduitAPIMethod' => 'applications/files/conduit/FileConduitAPIMethod.php',
     'FileCreateMailReceiver' => 'applications/files/mail/FileCreateMailReceiver.php',
+    'FileDeletionWorker' => 'applications/files/worker/FileDeletionWorker.php',
     'FileDownloadConduitAPIMethod' => 'applications/files/conduit/FileDownloadConduitAPIMethod.php',
     'FileInfoConduitAPIMethod' => 'applications/files/conduit/FileInfoConduitAPIMethod.php',
     'FileMailReceiver' => 'applications/files/mail/FileMailReceiver.php',
@@ -5977,6 +5978,7 @@
     'FileAllocateConduitAPIMethod' => 'FileConduitAPIMethod',
     'FileConduitAPIMethod' => 'ConduitAPIMethod',
     'FileCreateMailReceiver' => 'PhabricatorMailReceiver',
+    'FileDeletionWorker' => 'PhabricatorWorker',
     'FileDownloadConduitAPIMethod' => 'FileConduitAPIMethod',
     'FileInfoConduitAPIMethod' => 'FileConduitAPIMethod',
     'FileMailReceiver' => 'PhabricatorObjectMailReceiver',
diff --git a/src/applications/files/controller/PhabricatorFileDataController.php b/src/applications/files/controller/PhabricatorFileDataController.php
--- a/src/applications/files/controller/PhabricatorFileDataController.php
+++ b/src/applications/files/controller/PhabricatorFileDataController.php
@@ -143,6 +143,7 @@
     $file = id(new PhabricatorFileQuery())
       ->setViewer($viewer)
       ->withPHIDs(array($this->phid))
+      ->withIsDeleted(false)
       ->executeOne();
 
     if (!$file) {
diff --git a/src/applications/files/controller/PhabricatorFileDeleteController.php b/src/applications/files/controller/PhabricatorFileDeleteController.php
--- a/src/applications/files/controller/PhabricatorFileDeleteController.php
+++ b/src/applications/files/controller/PhabricatorFileDeleteController.php
@@ -9,6 +9,7 @@
     $file = id(new PhabricatorFileQuery())
       ->setViewer($viewer)
       ->withIDs(array($id))
+      ->withIsDeleted(false)
       ->requireCapabilities(
         array(
           PhabricatorPolicyCapability::CAN_VIEW,
@@ -25,8 +26,15 @@
     }
 
     if ($request->isFormPost()) {
-      $engine = new PhabricatorDestructionEngine();
-      $engine->destroyObject($file);
+      // Mark the file for deletion, save it, and schedule a worker to
+      // sweep by later and pick it up.
+      $file->setIsDeleted(true)->save();
+
+      PhabricatorWorker::scheduleTask(
+        'FileDeletionWorker',
+        array('objectPHID' => $file->getPHID()),
+        array('priority' => PhabricatorWorker::PRIORITY_BULK));
+
       return id(new AphrontRedirectResponse())->setURI('/file/');
     }
 
diff --git a/src/applications/files/controller/PhabricatorFileInfoController.php b/src/applications/files/controller/PhabricatorFileInfoController.php
--- a/src/applications/files/controller/PhabricatorFileInfoController.php
+++ b/src/applications/files/controller/PhabricatorFileInfoController.php
@@ -15,6 +15,7 @@
       $file = id(new PhabricatorFileQuery())
         ->setViewer($viewer)
         ->withPHIDs(array($phid))
+        ->withIsDeleted(false)
         ->executeOne();
 
       if (!$file) {
@@ -25,6 +26,7 @@
     $file = id(new PhabricatorFileQuery())
       ->setViewer($viewer)
       ->withIDs(array($id))
+      ->withIsDeleted(false)
       ->executeOne();
     if (!$file) {
       return new Aphront404Response();
diff --git a/src/applications/files/editor/PhabricatorFileEditEngine.php b/src/applications/files/editor/PhabricatorFileEditEngine.php
--- a/src/applications/files/editor/PhabricatorFileEditEngine.php
+++ b/src/applications/files/editor/PhabricatorFileEditEngine.php
@@ -36,7 +36,9 @@
   }
 
   protected function newObjectQuery() {
-    return new PhabricatorFileQuery();
+    $query = new PhabricatorFileQuery();
+    $query->withIsDeleted(false);
+    return $query;
   }
 
   protected function getObjectCreateTitleText($object) {
diff --git a/src/applications/files/query/PhabricatorFileQuery.php b/src/applications/files/query/PhabricatorFileQuery.php
--- a/src/applications/files/query/PhabricatorFileQuery.php
+++ b/src/applications/files/query/PhabricatorFileQuery.php
@@ -15,6 +15,7 @@
   private $maxLength;
   private $names;
   private $isPartial;
+  private $isDeleted;
   private $needTransforms;
   private $builtinKeys;
 
@@ -119,6 +120,11 @@
     return $this;
   }
 
+  public function withIsDeleted($deleted) {
+    $this->isDeleted = $deleted;
+    return $this;
+  }
+
   public function withNameNgrams($ngrams) {
     return $this->withNgramsConstraint(
       id(new PhabricatorFileNameNgrams()),
@@ -396,6 +402,13 @@
         (int)$this->isPartial);
     }
 
+    if ($this->isDeleted !== null) {
+      $where[] = qsprintf(
+        $conn,
+        'isDeleted = %d',
+        (int)$this->isDeleted);
+    }
+
     if ($this->builtinKeys !== null) {
       $where[] = qsprintf(
         $conn,
diff --git a/src/applications/files/query/PhabricatorFileSearchEngine.php b/src/applications/files/query/PhabricatorFileSearchEngine.php
--- a/src/applications/files/query/PhabricatorFileSearchEngine.php
+++ b/src/applications/files/query/PhabricatorFileSearchEngine.php
@@ -16,7 +16,9 @@
   }
 
   public function newQuery() {
-    return new PhabricatorFileQuery();
+    $query = new PhabricatorFileQuery();
+    $query->withIsDeleted(false);
+    return $query;
   }
 
   protected function buildCustomSearchFields() {
diff --git a/src/applications/files/storage/PhabricatorFile.php b/src/applications/files/storage/PhabricatorFile.php
--- a/src/applications/files/storage/PhabricatorFile.php
+++ b/src/applications/files/storage/PhabricatorFile.php
@@ -59,6 +59,7 @@
   protected $isExplicitUpload = 1;
   protected $viewPolicy = PhabricatorPolicies::POLICY_USER;
   protected $isPartial = 0;
+  protected $isDeleted = 0;
 
   private $objects = self::ATTACHABLE;
   private $objectPHIDs = self::ATTACHABLE;
@@ -103,6 +104,7 @@
         'mailKey' => 'bytes20',
         'isPartial' => 'bool',
         'builtinKey' => 'text64?',
+        'isDeleted' => 'bool',
       ),
       self::CONFIG_KEY_SCHEMA => array(
         'key_phid' => null,
diff --git a/src/applications/files/worker/FileDeletionWorker.php b/src/applications/files/worker/FileDeletionWorker.php
new file mode 100644
--- /dev/null
+++ b/src/applications/files/worker/FileDeletionWorker.php
@@ -0,0 +1,31 @@
+<?php
+
+final class FileDeletionWorker extends PhabricatorWorker {
+
+  private function loadFile() {
+    $phid = idx($this->getTaskData(), 'objectPHID');
+    if (!$phid) {
+      throw new PhabricatorWorkerPermanentFailureException(
+        pht('No "%s" in task data.', 'objectPHID'));
+    }
+
+    $file = id(new PhabricatorFileQuery())
+      ->setViewer(PhabricatorUser::getOmnipotentUser())
+      ->withPHIDs(array($phid))
+      ->executeOne();
+
+    if (!$file) {
+      throw new PhabricatorWorkerPermanentFailureException(
+        pht('File "%s" does not exist.', $phid));
+    }
+
+    return $file;
+  }
+
+  protected function doWork() {
+    $file = $this->loadFile();
+    $engine = new PhabricatorDestructionEngine();
+    $engine->destroyObject($file);
+  }
+
+}