diff --git a/resources/sql/autopatches/20160617.harbormaster.01.arelease.sql b/resources/sql/autopatches/20160617.harbormaster.01.arelease.sql
new file mode 100644
--- /dev/null
+++ b/resources/sql/autopatches/20160617.harbormaster.01.arelease.sql
@@ -0,0 +1,2 @@
+ALTER TABLE {$NAMESPACE}_harbormaster.harbormaster_buildartifact
+  ADD isReleased BOOL NOT NULL;
diff --git a/src/applications/harbormaster/engine/HarbormasterBuildEngine.php b/src/applications/harbormaster/engine/HarbormasterBuildEngine.php
--- a/src/applications/harbormaster/engine/HarbormasterBuildEngine.php
+++ b/src/applications/harbormaster/engine/HarbormasterBuildEngine.php
@@ -9,6 +9,7 @@
   private $build;
   private $viewer;
   private $newBuildTargets = array();
+  private $artifactReleaseQueue = array();
   private $forceBuildableUpdate;
 
   public function setForceBuildableUpdate($force_buildable_update) {
@@ -94,6 +95,8 @@
       $this->updateBuildable($build->getBuildable());
     }
 
+    $this->releaseQueuedArtifacts();
+
     // If we are no longer building for any reason, release all artifacts.
     if (!$build->isBuilding()) {
       $this->releaseAllArtifacts($build);
@@ -149,20 +152,21 @@
   }
 
   private function updateBuildSteps(HarbormasterBuild $build) {
-    $targets = id(new HarbormasterBuildTargetQuery())
+    $all_targets = id(new HarbormasterBuildTargetQuery())
       ->setViewer($this->getViewer())
       ->withBuildPHIDs(array($build->getPHID()))
       ->withBuildGenerations(array($build->getBuildGeneration()))
       ->execute();
 
-    $this->updateWaitingTargets($targets);
+    $this->updateWaitingTargets($all_targets);
 
-    $targets = mgroup($targets, 'getBuildStepPHID');
+    $targets = mgroup($all_targets, 'getBuildStepPHID');
 
     $steps = id(new HarbormasterBuildStepQuery())
       ->setViewer($this->getViewer())
       ->withBuildPlanPHIDs(array($build->getBuildPlan()->getPHID()))
       ->execute();
+    $steps = mpull($steps, null, 'getPHID');
 
     // Identify steps which are in various states.
 
@@ -252,6 +256,12 @@
       return;
     }
 
+    // Release any artifacts which are not inputs to any remaining build
+    // step. We're done with these, so something else is free to use them.
+    $ongoing_phids = array_keys($queued + $waiting + $underway);
+    $ongoing_steps = array_select_keys($steps, $ongoing_phids);
+    $this->releaseUnusedArtifacts($all_targets, $ongoing_steps);
+
     // Identify all the steps which are ready to run (because all their
     // dependencies are complete).
 
@@ -295,6 +305,59 @@
 
 
   /**
+   * Release any artifacts which aren't used by any running or waiting steps.
+   *
+   * This releases artifacts as soon as they're no longer used. This can be
+   * particularly relevant when a build uses multiple hosts since it returns
+   * hosts to the pool more quickly.
+   *
+   * @param list<HarbormasterBuildTarget> Targets in the build.
+   * @param list<HarbormasterBuildStep> List of running and waiting steps.
+   * @return void
+   */
+  private function releaseUnusedArtifacts(array $targets, array $steps) {
+    assert_instances_of($targets, 'HarbormasterBuildTarget');
+    assert_instances_of($steps, 'HarbormasterBuildStep');
+
+    if (!$targets || !$steps) {
+      return;
+    }
+
+    $target_phids = mpull($targets, 'getPHID');
+
+    $artifacts = id(new HarbormasterBuildArtifactQuery())
+      ->setViewer($this->getViewer())
+      ->withBuildTargetPHIDs($target_phids)
+      ->withIsReleased(false)
+      ->execute();
+    if (!$artifacts) {
+      return;
+    }
+
+    // Collect all the artifacts that remaining build steps accept as inputs.
+    $must_keep = array();
+    foreach ($steps as $step) {
+      $inputs = $step->getStepImplementation()->getArtifactInputs();
+      foreach ($inputs as $input) {
+        $artifact_key = $input['key'];
+        $must_keep[$artifact_key] = true;
+      }
+    }
+
+    // Queue unreleased artifacts which no remaining step uses for immediate
+    // release.
+    foreach ($artifacts as $artifact) {
+      $key = $artifact->getArtifactKey();
+      if (isset($must_keep[$key])) {
+        continue;
+      }
+
+      $this->artifactReleaseQueue[] = $artifact;
+    }
+  }
+
+
+  /**
    * Process messages which were sent to these targets, kicking applicable
    * targets out of "Waiting" and into either "Passed" or "Failed".
    *
@@ -488,12 +551,18 @@
     $artifacts = id(new HarbormasterBuildArtifactQuery())
       ->setViewer(PhabricatorUser::getOmnipotentUser())
       ->withBuildTargetPHIDs($target_phids)
+      ->withIsReleased(false)
       ->execute();
-
     foreach ($artifacts as $artifact) {
       $artifact->releaseArtifact();
     }
+  }
 
+  private function releaseQueuedArtifacts() {
+    foreach ($this->artifactReleaseQueue as $key => $artifact) {
+      $artifact->releaseArtifact();
+      unset($this->artifactReleaseQueue[$key]);
+    }
   }
 
 }
diff --git a/src/applications/harbormaster/query/HarbormasterBuildArtifactQuery.php b/src/applications/harbormaster/query/HarbormasterBuildArtifactQuery.php
--- a/src/applications/harbormaster/query/HarbormasterBuildArtifactQuery.php
+++ b/src/applications/harbormaster/query/HarbormasterBuildArtifactQuery.php
@@ -9,6 +9,7 @@
   private $artifactIndexes;
   private $keyBuildPHID;
   private $keyBuildGeneration;
+  private $isReleased;
 
   public function withIDs(array $ids) {
     $this->ids = $ids;
@@ -30,6 +31,11 @@
     return $this;
   }
 
+  public function withIsReleased($released) {
+    $this->isReleased = $released;
+    return $this;
+  }
+
   public function newResultObject() {
     return new HarbormasterBuildArtifact();
   }
@@ -94,6 +100,13 @@
         $this->artifactIndexes);
     }
 
+    if ($this->isReleased !== null) {
+      $where[] = qsprintf(
+        $conn,
+        'isReleased = %d',
+        (int)$this->isReleased);
+    }
+
     return $where;
   }
 
diff --git a/src/applications/harbormaster/step/HarbormasterBuildStepImplementation.php b/src/applications/harbormaster/step/HarbormasterBuildStepImplementation.php
--- a/src/applications/harbormaster/step/HarbormasterBuildStepImplementation.php
+++ b/src/applications/harbormaster/step/HarbormasterBuildStepImplementation.php
@@ -103,11 +103,6 @@
   /**
    * Return the name of artifacts produced by this command.
    *
-   * Something like:
-   *
-   *   return array(
-   *     'some_name_input_by_user' => 'host');
-   *
    * Future steps will calculate all available artifact mappings
    * before them and filter on the type.
    *
diff --git a/src/applications/harbormaster/storage/build/HarbormasterBuildArtifact.php b/src/applications/harbormaster/storage/build/HarbormasterBuildArtifact.php
--- a/src/applications/harbormaster/storage/build/HarbormasterBuildArtifact.php
+++ b/src/applications/harbormaster/storage/build/HarbormasterBuildArtifact.php
@@ -8,6 +8,7 @@
   protected $artifactIndex;
   protected $artifactKey;
   protected $artifactData = array();
+  protected $isReleased = 0;
 
   private $buildTarget = self::ATTACHABLE;
   private $artifactImplementation;
@@ -29,6 +30,7 @@
         'artifactType' => 'text32',
         'artifactIndex' => 'bytes12',
         'artifactKey' => 'text255',
+        'isReleased' => 'bool',
       ),
       self::CONFIG_KEY_SCHEMA => array(
         'key_artifact' => array(
@@ -83,13 +85,18 @@
   }
 
   public function releaseArtifact() {
-    $impl = $this->getArtifactImplementation();
+    if ($this->getIsReleased()) {
+      return $this;
+    }
 
+    $impl = $this->getArtifactImplementation();
     if ($impl) {
       $impl->releaseArtifact(PhabricatorUser::getOmnipotentUser());
     }
 
-    return null;
+    return $this
+      ->setIsReleased(1)
+      ->save();
   }
 
   public function getArtifactImplementation() {