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
@@ -2099,6 +2099,7 @@
     'PhabricatorAuthPasswordRevoker' => 'applications/auth/revoker/PhabricatorAuthPasswordRevoker.php',
     'PhabricatorAuthPasswordTestCase' => 'applications/auth/__tests__/PhabricatorAuthPasswordTestCase.php',
     'PhabricatorAuthPasswordTransaction' => 'applications/auth/storage/PhabricatorAuthPasswordTransaction.php',
+    'PhabricatorAuthPasswordTransactionQuery' => 'applications/auth/query/PhabricatorAuthPasswordTransactionQuery.php',
     'PhabricatorAuthPasswordTransactionType' => 'applications/auth/xaction/PhabricatorAuthPasswordTransactionType.php',
     'PhabricatorAuthPasswordUpgradeTransaction' => 'applications/auth/xaction/PhabricatorAuthPasswordUpgradeTransaction.php',
     'PhabricatorAuthProvider' => 'applications/auth/provider/PhabricatorAuthProvider.php',
@@ -7393,6 +7394,7 @@
     'PhabricatorAuthPasswordRevoker' => 'PhabricatorAuthRevoker',
     'PhabricatorAuthPasswordTestCase' => 'PhabricatorTestCase',
     'PhabricatorAuthPasswordTransaction' => 'PhabricatorModularTransaction',
+    'PhabricatorAuthPasswordTransactionQuery' => 'PhabricatorApplicationTransactionQuery',
     'PhabricatorAuthPasswordTransactionType' => 'PhabricatorModularTransactionType',
     'PhabricatorAuthPasswordUpgradeTransaction' => 'PhabricatorAuthPasswordTransactionType',
     'PhabricatorAuthProvider' => 'Phobject',
diff --git a/src/applications/auth/__tests__/PhabricatorAuthPasswordTestCase.php b/src/applications/auth/__tests__/PhabricatorAuthPasswordTestCase.php
--- a/src/applications/auth/__tests__/PhabricatorAuthPasswordTestCase.php
+++ b/src/applications/auth/__tests__/PhabricatorAuthPasswordTestCase.php
@@ -99,6 +99,91 @@
     $this->assertTrue($account_engine->isUniquePassword($password2));
   }
 
+  public function testPasswordUpgrade() {
+    $weak_hasher = new PhabricatorIteratedMD5PasswordHasher();
+
+    // Make sure we have two different hashers, and that the second one is
+    // stronger than iterated MD5. The most common reason this would fail is
+    // if an install does not have bcrypt available.
+    $strong_hasher = PhabricatorPasswordHasher::getBestHasher();
+    if ($strong_hasher->getStrength() <= $weak_hasher->getStrength()) {
+      $this->assertSkipped(
+        pht(
+          'Multiple password hashers of different strengths are not '.
+          'available, so hash upgrading can not be tested.'));
+    }
+
+    $envelope = new PhutilOpaqueEnvelope('lunar1997');
+
+    $user = $this->generateNewTestUser();
+    $type = PhabricatorAuthPassword::PASSWORD_TYPE_TEST;
+    $content_source = $this->newContentSource();
+
+    $engine = id(new PhabricatorAuthPasswordEngine())
+      ->setViewer($user)
+      ->setContentSource($content_source)
+      ->setPasswordType($type)
+      ->setObject($user);
+
+    $password = PhabricatorAuthPassword::initializeNewPassword($user, $type)
+      ->setPasswordWithHasher($envelope, $user, $weak_hasher)
+      ->save();
+
+    $weak_name = $weak_hasher->getHashName();
+    $strong_name = $strong_hasher->getHashName();
+
+    // Since we explicitly used the weak hasher, the password should have
+    // been hashed with it.
+    $actual_hasher = $password->getHasher();
+    $this->assertEqual($weak_name, $actual_hasher->getHashName());
+
+    $is_valid = $engine
+      ->setUpgradeHashers(false)
+      ->isValidPassword($envelope, $user);
+    $password->reload();
+
+    // Since we disabled hasher upgrading, the password should not have been
+    // rehashed.
+    $this->assertTrue($is_valid);
+    $actual_hasher = $password->getHasher();
+    $this->assertEqual($weak_name, $actual_hasher->getHashName());
+
+    $is_valid = $engine
+      ->setUpgradeHashers(true)
+      ->isValidPassword($envelope, $user);
+    $password->reload();
+
+    // Now that we enabled hasher upgrading, the password should have been
+    // automatically rehashed into the stronger format.
+    $this->assertTrue($is_valid);
+    $actual_hasher = $password->getHasher();
+    $this->assertEqual($strong_name, $actual_hasher->getHashName());
+
+    // We should also have an "upgrade" transaction in the transaction record
+    // now which records the two hasher names.
+    $xactions = id(new PhabricatorAuthPasswordTransactionQuery())
+      ->setViewer($user)
+      ->withObjectPHIDs(array($password->getPHID()))
+      ->withTransactionTypes(
+        array(
+          PhabricatorAuthPasswordUpgradeTransaction::TRANSACTIONTYPE,
+        ))
+      ->execute();
+
+    $this->assertEqual(1, count($xactions));
+    $xaction = head($xactions);
+
+    $this->assertEqual($weak_name, $xaction->getOldValue());
+    $this->assertEqual($strong_name, $xaction->getNewValue());
+
+    $is_valid = $engine
+      ->isValidPassword($envelope, $user);
+
+    // Finally, the password should still be valid after all the dust has
+    // settled.
+    $this->assertTrue($is_valid);
+  }
+
   private function revokePassword(
     PhabricatorUser $actor,
     PhabricatorAuthPassword $password) {
diff --git a/src/applications/auth/editor/PhabricatorAuthPasswordEditor.php b/src/applications/auth/editor/PhabricatorAuthPasswordEditor.php
--- a/src/applications/auth/editor/PhabricatorAuthPasswordEditor.php
+++ b/src/applications/auth/editor/PhabricatorAuthPasswordEditor.php
@@ -3,6 +3,17 @@
 final class PhabricatorAuthPasswordEditor
   extends PhabricatorApplicationTransactionEditor {
 
+  private $oldHasher;
+
+  public function setOldHasher(PhabricatorPasswordHasher $old_hasher) {
+    $this->oldHasher = $old_hasher;
+    return $this;
+  }
+
+  public function getOldHasher() {
+    return $this->oldHasher;
+  }
+
   public function getEditorApplicationClass() {
     return 'PhabricatorAuthApplication';
   }
diff --git a/src/applications/auth/engine/PhabricatorAuthPasswordEngine.php b/src/applications/auth/engine/PhabricatorAuthPasswordEngine.php
--- a/src/applications/auth/engine/PhabricatorAuthPasswordEngine.php
+++ b/src/applications/auth/engine/PhabricatorAuthPasswordEngine.php
@@ -224,7 +224,6 @@
 
       $xactions[] = $password->getApplicationTransactionTemplate()
         ->setTransactionType($upgrade_type)
-        ->setOldValue($old_hasher->getHashName())
         ->setNewValue($new_hasher->getHashName());
 
       $editor = $password->getApplicationTransactionEditor()
@@ -232,6 +231,7 @@
         ->setContinueOnNoEffect(true)
         ->setContinueOnMissingFields(true)
         ->setContentSource($content_source)
+        ->setOldHasher($old_hasher)
         ->applyTransactions($password, $xactions);
     }
     unset($unguarded);
diff --git a/src/applications/auth/query/PhabricatorAuthPasswordTransactionQuery.php b/src/applications/auth/query/PhabricatorAuthPasswordTransactionQuery.php
new file mode 100644
--- /dev/null
+++ b/src/applications/auth/query/PhabricatorAuthPasswordTransactionQuery.php
@@ -0,0 +1,10 @@
+<?php
+
+final class PhabricatorAuthPasswordTransactionQuery
+  extends PhabricatorApplicationTransactionQuery {
+
+  public function getTemplateApplicationTransaction() {
+    return new PhabricatorAuthPasswordTransaction();
+  }
+
+}
diff --git a/src/applications/auth/xaction/PhabricatorAuthPasswordUpgradeTransaction.php b/src/applications/auth/xaction/PhabricatorAuthPasswordUpgradeTransaction.php
--- a/src/applications/auth/xaction/PhabricatorAuthPasswordUpgradeTransaction.php
+++ b/src/applications/auth/xaction/PhabricatorAuthPasswordUpgradeTransaction.php
@@ -6,11 +6,17 @@
   const TRANSACTIONTYPE = 'password.upgrade';
 
   public function generateOldValue($object) {
-    return $this->getStorage()->getOldValue();
+    $old_hasher = $this->getEditor()->getOldHasher();
+
+    if (!$old_hasher) {
+      throw new PhutilInvalidStateException('setOldHasher');
+    }
+
+    return $old_hasher->getHashName();
   }
 
   public function generateNewValue($object, $value) {
-    return (bool)$value;
+    return $value;
   }
 
   public function getTitle() {