diff --git a/resources/sql/autopatches/20160518.ssh.01.activecol.sql b/resources/sql/autopatches/20160518.ssh.01.activecol.sql
new file mode 100644
--- /dev/null
+++ b/resources/sql/autopatches/20160518.ssh.01.activecol.sql
@@ -0,0 +1,2 @@
+ALTER TABLE {$NAMESPACE}_auth.auth_sshkey
+  ADD isActive BOOL;
diff --git a/resources/sql/autopatches/20160518.ssh.02.activeval.sql b/resources/sql/autopatches/20160518.ssh.02.activeval.sql
new file mode 100644
--- /dev/null
+++ b/resources/sql/autopatches/20160518.ssh.02.activeval.sql
@@ -0,0 +1,2 @@
+UPDATE {$NAMESPACE}_auth.auth_sshkey
+  SET isActive = 1;
diff --git a/resources/sql/autopatches/20160518.ssh.03.activekey.sql b/resources/sql/autopatches/20160518.ssh.03.activekey.sql
new file mode 100644
--- /dev/null
+++ b/resources/sql/autopatches/20160518.ssh.03.activekey.sql
@@ -0,0 +1,2 @@
+ALTER TABLE {$NAMESPACE}_auth.auth_sshkey
+  ADD UNIQUE KEY `key_activeunique` (keyIndex, isActive);
diff --git a/scripts/ssh/ssh-auth-key.php b/scripts/ssh/ssh-auth-key.php
--- a/scripts/ssh/ssh-auth-key.php
+++ b/scripts/ssh/ssh-auth-key.php
@@ -14,6 +14,7 @@
 $key = id(new PhabricatorAuthSSHKeyQuery())
   ->setViewer(PhabricatorUser::getOmnipotentUser())
   ->withKeys(array($public_key))
+  ->withIsActive(true)
   ->executeOne();
 if (!$key) {
   exit(1);
diff --git a/scripts/ssh/ssh-auth.php b/scripts/ssh/ssh-auth.php
--- a/scripts/ssh/ssh-auth.php
+++ b/scripts/ssh/ssh-auth.php
@@ -6,6 +6,7 @@
 
 $keys = id(new PhabricatorAuthSSHKeyQuery())
   ->setViewer(PhabricatorUser::getOmnipotentUser())
+  ->withIsActive(true)
   ->execute();
 
 if (!$keys) {
diff --git a/src/applications/almanac/controller/AlmanacDeviceViewController.php b/src/applications/almanac/controller/AlmanacDeviceViewController.php
--- a/src/applications/almanac/controller/AlmanacDeviceViewController.php
+++ b/src/applications/almanac/controller/AlmanacDeviceViewController.php
@@ -146,6 +146,7 @@
     $keys = id(new PhabricatorAuthSSHKeyQuery())
       ->setViewer($viewer)
       ->withObjectPHIDs(array($device_phid))
+      ->withIsActive(true)
       ->execute();
 
     $table = id(new PhabricatorAuthSSHKeyTableView())
diff --git a/src/applications/almanac/management/AlmanacManagementRegisterWorkflow.php b/src/applications/almanac/management/AlmanacManagementRegisterWorkflow.php
--- a/src/applications/almanac/management/AlmanacManagementRegisterWorkflow.php
+++ b/src/applications/almanac/management/AlmanacManagementRegisterWorkflow.php
@@ -141,6 +141,7 @@
     $public_key = id(new PhabricatorAuthSSHKeyQuery())
       ->setViewer($this->getViewer())
       ->withKeys(array($key_object))
+      ->withIsActive(true)
       ->executeOne();
 
     if (!$public_key) {
diff --git a/src/applications/almanac/management/AlmanacManagementTrustKeyWorkflow.php b/src/applications/almanac/management/AlmanacManagementTrustKeyWorkflow.php
--- a/src/applications/almanac/management/AlmanacManagementTrustKeyWorkflow.php
+++ b/src/applications/almanac/management/AlmanacManagementTrustKeyWorkflow.php
@@ -35,6 +35,11 @@
         pht('No public key exists with ID "%s".', $id));
     }
 
+    if (!$key->getIsActive()) {
+      throw new PhutilArgumentUsageException(
+        pht('Public key "%s" is not an active key.', $id));
+    }
+
     if ($key->getIsTrusted()) {
       throw new PhutilArgumentUsageException(
         pht('Public key with ID %s is already trusted.', $id));
diff --git a/src/applications/auth/conduit/PhabricatorAuthQueryPublicKeysConduitAPIMethod.php b/src/applications/auth/conduit/PhabricatorAuthQueryPublicKeysConduitAPIMethod.php
--- a/src/applications/auth/conduit/PhabricatorAuthQueryPublicKeysConduitAPIMethod.php
+++ b/src/applications/auth/conduit/PhabricatorAuthQueryPublicKeysConduitAPIMethod.php
@@ -28,7 +28,8 @@
     $viewer = $request->getUser();
 
     $query = id(new PhabricatorAuthSSHKeyQuery())
-      ->setViewer($viewer);
+      ->setViewer($viewer)
+      ->withIsActive(true);
 
     $ids = $request->getValue('ids');
     if ($ids !== null) {
diff --git a/src/applications/auth/controller/PhabricatorAuthSSHKeyController.php b/src/applications/auth/controller/PhabricatorAuthSSHKeyController.php
--- a/src/applications/auth/controller/PhabricatorAuthSSHKeyController.php
+++ b/src/applications/auth/controller/PhabricatorAuthSSHKeyController.php
@@ -25,9 +25,7 @@
       return null;
     }
 
-    return id(new PhabricatorAuthSSHKey())
-      ->setObjectPHID($object_phid)
-      ->attachObject($object);
+    return PhabricatorAuthSSHKey::initializeNewSSHKey($viewer, $object);
   }
 
 }
diff --git a/src/applications/auth/controller/PhabricatorAuthSSHKeyDeleteController.php b/src/applications/auth/controller/PhabricatorAuthSSHKeyDeleteController.php
--- a/src/applications/auth/controller/PhabricatorAuthSSHKeyDeleteController.php
+++ b/src/applications/auth/controller/PhabricatorAuthSSHKeyDeleteController.php
@@ -9,6 +9,7 @@
     $key = id(new PhabricatorAuthSSHKeyQuery())
       ->setViewer($viewer)
       ->withIDs(array($request->getURIData('id')))
+      ->withIsActive(true)
       ->requireCapabilities(
         array(
           PhabricatorPolicyCapability::CAN_VIEW,
@@ -27,8 +28,11 @@
       $cancel_uri);
 
     if ($request->isFormPost()) {
-      // TODO: It would be nice to write an edge transaction here or something.
-      $key->delete();
+
+      // TODO: Convert to transactions.
+      $key->setIsActive(null);
+      $key->save();
+
       return id(new AphrontRedirectResponse())->setURI($cancel_uri);
     }
 
diff --git a/src/applications/auth/controller/PhabricatorAuthSSHKeyEditController.php b/src/applications/auth/controller/PhabricatorAuthSSHKeyEditController.php
--- a/src/applications/auth/controller/PhabricatorAuthSSHKeyEditController.php
+++ b/src/applications/auth/controller/PhabricatorAuthSSHKeyEditController.php
@@ -11,6 +11,7 @@
       $key = id(new PhabricatorAuthSSHKeyQuery())
         ->setViewer($viewer)
         ->withIDs(array($id))
+        ->withIsActive(true)
         ->requireCapabilities(
           array(
             PhabricatorPolicyCapability::CAN_VIEW,
diff --git a/src/applications/auth/phid/PhabricatorAuthSSHKeyPHIDType.php b/src/applications/auth/phid/PhabricatorAuthSSHKeyPHIDType.php
--- a/src/applications/auth/phid/PhabricatorAuthSSHKeyPHIDType.php
+++ b/src/applications/auth/phid/PhabricatorAuthSSHKeyPHIDType.php
@@ -32,6 +32,10 @@
     foreach ($handles as $phid => $handle) {
       $key = $objects[$phid];
       $handle->setName(pht('SSH Key %d', $key->getID()));
+
+      if (!$key->getIsActive()) {
+        $handle->setClosed(pht('Inactive'));
+      }
     }
   }
 
diff --git a/src/applications/auth/query/PhabricatorAuthSSHKeyQuery.php b/src/applications/auth/query/PhabricatorAuthSSHKeyQuery.php
--- a/src/applications/auth/query/PhabricatorAuthSSHKeyQuery.php
+++ b/src/applications/auth/query/PhabricatorAuthSSHKeyQuery.php
@@ -7,6 +7,7 @@
   private $phids;
   private $objectPHIDs;
   private $keys;
+  private $isActive;
 
   public function withIDs(array $ids) {
     $this->ids = $ids;
@@ -29,6 +30,11 @@
     return $this;
   }
 
+  public function withIsActive($active) {
+    $this->isActive = $active;
+    return $this;
+  }
+
   public function newResultObject() {
     return new PhabricatorAuthSSHKey();
   }
@@ -100,6 +106,19 @@
       $where[] = implode(' OR ', $sql);
     }
 
+    if ($this->isActive !== null) {
+      if ($this->isActive) {
+        $where[] = qsprintf(
+          $conn,
+          'isActive = %d',
+          1);
+      } else {
+        $where[] = qsprintf(
+          $conn,
+          'isActive IS NULL');
+      }
+    }
+
     return $where;
 
   }
diff --git a/src/applications/auth/storage/PhabricatorAuthSSHKey.php b/src/applications/auth/storage/PhabricatorAuthSSHKey.php
--- a/src/applications/auth/storage/PhabricatorAuthSSHKey.php
+++ b/src/applications/auth/storage/PhabricatorAuthSSHKey.php
@@ -13,9 +13,28 @@
   protected $keyBody;
   protected $keyComment = '';
   protected $isTrusted = 0;
+  protected $isActive;
 
   private $object = self::ATTACHABLE;
 
+  public static function initializeNewSSHKey(
+    PhabricatorUser $viewer,
+    PhabricatorSSHPublicKeyInterface $object) {
+
+    // You must be able to edit an object to create a new key on it.
+    PhabricatorPolicyFilter::requireCapability(
+      $viewer,
+      $object,
+      PhabricatorPolicyCapability::CAN_EDIT);
+
+    $object_phid = $object->getPHID();
+
+    return id(new self())
+      ->setIsActive(1)
+      ->setObjectPHID($object_phid)
+      ->attachObject($object);
+  }
+
   protected function getConfiguration() {
     return array(
       self::CONFIG_AUX_PHID => true,
@@ -26,13 +45,19 @@
         'keyBody' => 'text',
         'keyComment' => 'text255',
         'isTrusted' => 'bool',
+        'isActive' => 'bool?',
       ),
       self::CONFIG_KEY_SCHEMA => array(
         'key_object' => array(
           'columns' => array('objectPHID'),
         ),
-        'key_unique' => array(
-          'columns' => array('keyIndex'),
+        'key_active' => array(
+          'columns' => array('isActive', 'objectPHID'),
+        ),
+        // NOTE: This unique key includes a nullable column, effectively
+        // constraining uniqueness on active keys only.
+        'key_activeunique' => array(
+          'columns' => array('keyIndex', 'isActive'),
           'unique' => true,
         ),
       ),
diff --git a/src/applications/conduit/controller/PhabricatorConduitAPIController.php b/src/applications/conduit/controller/PhabricatorConduitAPIController.php
--- a/src/applications/conduit/controller/PhabricatorConduitAPIController.php
+++ b/src/applications/conduit/controller/PhabricatorConduitAPIController.php
@@ -204,6 +204,7 @@
       $stored_key = id(new PhabricatorAuthSSHKeyQuery())
         ->setViewer(PhabricatorUser::getOmnipotentUser())
         ->withKeys(array($public_key))
+        ->withIsActive(true)
         ->executeOne();
       if (!$stored_key) {
         return array(
diff --git a/src/applications/people/storage/PhabricatorUser.php b/src/applications/people/storage/PhabricatorUser.php
--- a/src/applications/people/storage/PhabricatorUser.php
+++ b/src/applications/people/storage/PhabricatorUser.php
@@ -1291,11 +1291,12 @@
         $profile->delete();
       }
 
-      $keys = id(new PhabricatorAuthSSHKey())->loadAllWhere(
-        'objectPHID = %s',
-        $this->getPHID());
+      $keys = id(new PhabricatorAuthSSHKeyQuery())
+        ->setViewer($engine->getViewer())
+        ->withObjectPHIDs(array($this->getPHID()))
+        ->execute();
       foreach ($keys as $key) {
-        $key->delete();
+        $engine->destroyObject($key);
       }
 
       $emails = id(new PhabricatorUserEmail())->loadAllWhere(
diff --git a/src/applications/settings/panel/PhabricatorSSHKeysSettingsPanel.php b/src/applications/settings/panel/PhabricatorSSHKeysSettingsPanel.php
--- a/src/applications/settings/panel/PhabricatorSSHKeysSettingsPanel.php
+++ b/src/applications/settings/panel/PhabricatorSSHKeysSettingsPanel.php
@@ -33,6 +33,7 @@
     $keys = id(new PhabricatorAuthSSHKeyQuery())
       ->setViewer($viewer)
       ->withObjectPHIDs(array($user->getPHID()))
+      ->withIsActive(true)
       ->execute();
 
     $table = id(new PhabricatorAuthSSHKeyTableView())