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
@@ -4855,6 +4855,8 @@
       'PhabricatorMentionableInterface',
       'PhabricatorPolicyInterface',
       'PhabricatorProjectInterface',
+      'PhabricatorDestructibleInterface',
+      'PhabricatorApplicationTransactionInterface',
     ),
     'PhabricatorPasteApplication' => 'PhabricatorApplication',
     'PhabricatorPasteCommentController' => 'PhabricatorPasteController',
diff --git a/src/applications/paste/storage/PhabricatorPaste.php b/src/applications/paste/storage/PhabricatorPaste.php
--- a/src/applications/paste/storage/PhabricatorPaste.php
+++ b/src/applications/paste/storage/PhabricatorPaste.php
@@ -7,7 +7,9 @@
     PhabricatorFlaggableInterface,
     PhabricatorMentionableInterface,
     PhabricatorPolicyInterface,
-    PhabricatorProjectInterface {
+    PhabricatorProjectInterface,
+    PhabricatorDestructibleInterface,
+    PhabricatorApplicationTransactionInterface {
 
   protected $title;
   protected $authorPHID;
@@ -152,4 +154,40 @@
     return pht('The author of a paste can always view and edit it.');
   }
 
+
+/* -(  PhabricatorDestructibleInterface  )----------------------------------- */
+
+
+  public function destroyObjectPermanently(
+    PhabricatorDestructionEngine $engine) {
+
+    if ($this->filePHID) {
+      $file = id(new PhabricatorFileQuery())
+        ->setViewer(PhabricatorUser::getOmnipotentUser())
+        ->withPHIDs(array($this->filePHID))
+        ->executeOne();
+      if ($file) {
+        $engine->destroyObject($file);
+      }
+    }
+
+    $this->delete();
+  }
+
+
+/* -(  PhabricatorApplicationTransactionInterface  )------------------------- */
+
+
+  public function getApplicationTransactionEditor() {
+    return new PhabricatorPasteEditor();
+  }
+
+  public function getApplicationTransactionObject() {
+    return $this;
+  }
+
+  public function getApplicationTransactionTemplate() {
+    return new PhabricatorPasteTransaction();
+  }
+
 }