diff --git a/resources/sql/autopatches/20140706.harbormasterdepend.1.php b/resources/sql/autopatches/20140706.harbormasterdepend.1.php
new file mode 100644
--- /dev/null
+++ b/resources/sql/autopatches/20140706.harbormasterdepend.1.php
@@ -0,0 +1,54 @@
+<?php
+
+$plan_table = new HarbormasterBuildPlan();
+$step_table = new HarbormasterBuildStep();
+$conn_w = $plan_table->establishConnection('w');
+foreach (new LiskMigrationIterator($plan_table) as $plan) {
+
+  echo pht(
+    "Migrating build plan %d: %s...\n",
+    $plan->getID(),
+    $plan->getName());
+
+  // Load all build steps in order using the step sequence.
+  $steps = queryfx_all(
+    $conn_w,
+    'SELECT id FROM %T WHERE buildPlanPHID = %s ORDER BY sequence ASC;',
+    $step_table->getTableName(),
+    $plan->getPHID());
+
+  $previous_step = null;
+  foreach ($steps as $step) {
+    $id = $step['id'];
+
+    $loaded_step = id(new HarbormasterBuildStep())->load($id);
+
+    $depends_on = $loaded_step->getDetail('dependsOn');
+    if ($depends_on !== null) {
+      // This plan already contains steps with depends_on set, so
+      // we skip since there's nothing to migrate.
+      break;
+    }
+
+    if ($previous_step === null) {
+      $depends_on = array();
+    } else {
+      $depends_on = array($previous_step->getPHID());
+    }
+
+    $loaded_step->setDetail('dependsOn', $depends_on);
+    queryfx(
+      $conn_w,
+      'UPDATE %T SET details = %s WHERE id = %d',
+      $step_table->getTableName(),
+      json_encode($loaded_step->getDetails()),
+      $loaded_step->getID());
+
+    $previous_step = $loaded_step;
+
+    echo pht(
+      "  Migrated build step %d.\n",
+      $loaded_step->getID());
+  }
+
+}
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
@@ -652,7 +652,9 @@
     'HarbormasterBuildArtifact' => 'applications/harbormaster/storage/build/HarbormasterBuildArtifact.php',
     'HarbormasterBuildArtifactQuery' => 'applications/harbormaster/query/HarbormasterBuildArtifactQuery.php',
     'HarbormasterBuildCommand' => 'applications/harbormaster/storage/HarbormasterBuildCommand.php',
+    'HarbormasterBuildDependencyDatasource' => 'applications/harbormaster/typeahead/HarbormasterBuildDependencyDatasource.php',
     'HarbormasterBuildEngine' => 'applications/harbormaster/engine/HarbormasterBuildEngine.php',
+    'HarbormasterBuildGraph' => 'applications/harbormaster/engine/HarbormasterBuildGraph.php',
     'HarbormasterBuildItem' => 'applications/harbormaster/storage/build/HarbormasterBuildItem.php',
     'HarbormasterBuildItemPHIDType' => 'applications/harbormaster/phid/HarbormasterBuildItemPHIDType.php',
     'HarbormasterBuildItemQuery' => 'applications/harbormaster/query/HarbormasterBuildItemQuery.php',
@@ -715,7 +717,6 @@
     'HarbormasterPlanDisableController' => 'applications/harbormaster/controller/HarbormasterPlanDisableController.php',
     'HarbormasterPlanEditController' => 'applications/harbormaster/controller/HarbormasterPlanEditController.php',
     'HarbormasterPlanListController' => 'applications/harbormaster/controller/HarbormasterPlanListController.php',
-    'HarbormasterPlanOrderController' => 'applications/harbormaster/controller/HarbormasterPlanOrderController.php',
     'HarbormasterPlanRunController' => 'applications/harbormaster/controller/HarbormasterPlanRunController.php',
     'HarbormasterPlanViewController' => 'applications/harbormaster/controller/HarbormasterPlanViewController.php',
     'HarbormasterPublishFragmentBuildStepImplementation' => 'applications/harbormaster/step/HarbormasterPublishFragmentBuildStepImplementation.php',
@@ -3391,7 +3392,9 @@
     ),
     'HarbormasterBuildArtifactQuery' => 'PhabricatorCursorPagedPolicyAwareQuery',
     'HarbormasterBuildCommand' => 'HarbormasterDAO',
+    'HarbormasterBuildDependencyDatasource' => 'PhabricatorTypeaheadDatasource',
     'HarbormasterBuildEngine' => 'Phobject',
+    'HarbormasterBuildGraph' => 'AbstractDirectedGraph',
     'HarbormasterBuildItem' => 'HarbormasterDAO',
     'HarbormasterBuildItemPHIDType' => 'PhabricatorPHIDType',
     'HarbormasterBuildItemQuery' => 'PhabricatorCursorPagedPolicyAwareQuery',
@@ -3476,7 +3479,6 @@
     'HarbormasterPlanDisableController' => 'HarbormasterPlanController',
     'HarbormasterPlanEditController' => 'HarbormasterPlanController',
     'HarbormasterPlanListController' => 'HarbormasterPlanController',
-    'HarbormasterPlanOrderController' => 'HarbormasterController',
     'HarbormasterPlanRunController' => 'HarbormasterController',
     'HarbormasterPlanViewController' => 'HarbormasterPlanController',
     'HarbormasterPublishFragmentBuildStepImplementation' => 'HarbormasterBuildStepImplementation',
diff --git a/src/applications/harbormaster/controller/HarbormasterBuildableViewController.php b/src/applications/harbormaster/controller/HarbormasterBuildableViewController.php
--- a/src/applications/harbormaster/controller/HarbormasterBuildableViewController.php
+++ b/src/applications/harbormaster/controller/HarbormasterBuildableViewController.php
@@ -179,29 +179,7 @@
         ->setHref($view_uri);
 
       $status = $build->getBuildStatus();
-      switch ($status) {
-        case HarbormasterBuild::STATUS_INACTIVE:
-          $item->setBarColor('grey');
-          break;
-        case HarbormasterBuild::STATUS_PENDING:
-          $item->setBarColor('blue');
-          break;
-        case HarbormasterBuild::STATUS_BUILDING:
-          $item->setBarColor('yellow');
-          break;
-        case HarbormasterBuild::STATUS_PASSED:
-          $item->setBarColor('green');
-          break;
-        case HarbormasterBuild::STATUS_FAILED:
-          $item->setBarColor('red');
-          break;
-        case HarbormasterBuild::STATUS_ERROR:
-          $item->setBarColor('red');
-          break;
-        case HarbormasterBuild::STATUS_STOPPED:
-          $item->setBarColor('black');
-          break;
-      }
+      $item->setBarColor(HarbormasterBuild::getBuildStatusColor($status));
 
       $item->addAttribute(HarbormasterBuild::getBuildStatusName($status));
 
diff --git a/src/applications/harbormaster/controller/HarbormasterPlanOrderController.php b/src/applications/harbormaster/controller/HarbormasterPlanOrderController.php
deleted file mode 100644
--- a/src/applications/harbormaster/controller/HarbormasterPlanOrderController.php
+++ /dev/null
@@ -1,53 +0,0 @@
-<?php
-
-final class HarbormasterPlanOrderController extends HarbormasterController {
-
-  private $id;
-
-  public function willProcessRequest(array $data) {
-    $this->id = idx($data, 'id');
-  }
-
-  public function processRequest() {
-    $request = $this->getRequest();
-    $user = $request->getUser();
-
-    $request->validateCSRF();
-
-    $this->requireApplicationCapability(
-      HarbormasterManagePlansCapability::CAPABILITY);
-
-    $plan = id(new HarbormasterBuildPlanQuery())
-      ->setViewer($user)
-      ->withIDs(array($this->id))
-      ->executeOne();
-    if (!$plan) {
-      return new Aphront404Response();
-    }
-
-    // Load all steps.
-    $order = $request->getStrList('order');
-    $steps = id(new HarbormasterBuildStepQuery())
-      ->setViewer($user)
-      ->withIDs($order)
-      ->execute();
-    $steps = array_select_keys($steps, $order);
-    $reordered_steps = array();
-
-    // Apply sequences.
-    $sequence = 1;
-    foreach ($steps as $step) {
-      $step->setSequence($sequence++);
-      $step->save();
-
-      $reordered_steps[] = $step;
-    }
-
-    // NOTE: Reordering steps may invalidate artifacts. This is fine; the UI
-    // will show that there are ordering issues.
-
-    // Force the page to re-render.
-    return id(new AphrontRedirectResponse());
-  }
-
-}
diff --git a/src/applications/harbormaster/controller/HarbormasterPlanViewController.php b/src/applications/harbormaster/controller/HarbormasterPlanViewController.php
--- a/src/applications/harbormaster/controller/HarbormasterPlanViewController.php
+++ b/src/applications/harbormaster/controller/HarbormasterPlanViewController.php
@@ -49,9 +49,21 @@
     $crumbs = $this->buildApplicationCrumbs();
     $crumbs->addTextCrumb(pht('Plan %d', $id));
 
-    list($step_list, $has_any_conflicts) = $this->buildStepList($plan);
+    list($step_list, $has_any_conflicts, $would_deadlock) =
+      $this->buildStepList($plan);
 
-    if ($has_any_conflicts) {
+    if ($would_deadlock) {
+      $box->setFormErrors(
+        array(
+          pht(
+            'This build plan will deadlock when executed, due to '.
+            'circular dependencies present in the build plan. '.
+            'Examine the step list and resolve the deadlock.'),
+        ));
+    } else if ($has_any_conflicts) {
+      // A deadlocking build will also cause all the artifacts to be
+      // invalid, so we just skip showing this message if that's the
+      // case.
       $box->setFormErrors(
         array(
           pht(
@@ -76,31 +88,37 @@
     $request = $this->getRequest();
     $viewer = $request->getUser();
 
-    $list_id = celerity_generate_unique_node_id();
+    $run_order =
+      HarbormasterBuildGraph::determineDependencyExecution($plan);
 
     $steps = id(new HarbormasterBuildStepQuery())
       ->setViewer($viewer)
       ->withBuildPlanPHIDs(array($plan->getPHID()))
       ->execute();
+    $steps = mpull($steps, null, 'getPHID');
 
     $can_edit = $this->hasApplicationCapability(
       HarbormasterManagePlansCapability::CAPABILITY);
 
-    $i = 1;
     $step_list = id(new PHUIObjectItemListView())
       ->setUser($viewer)
       ->setNoDataString(
-        pht('This build plan does not have any build steps yet.'))
-      ->setID($list_id);
-    Javelin::initBehavior(
-      'harbormaster-reorder-steps',
-      array(
-        'listID' => $list_id,
-        'orderURI' => '/harbormaster/plan/order/'.$plan->getID().'/',
-      ));
+        pht('This build plan does not have any build steps yet.'));
 
+    $i = 1;
+    $last_depth = 0;
     $has_any_conflicts = false;
-    foreach ($steps as $step) {
+    $is_deadlocking = false;
+    foreach ($run_order as $run_ref) {
+      $step = $steps[$run_ref['node']->getPHID()];
+      $depth = $run_ref['depth'] + 1;
+      if ($last_depth !== $depth) {
+        $last_depth = $depth;
+        $i = 1;
+      } else {
+        $i++;
+      }
+
       $implementation = null;
       try {
         $implementation = $step->getStepImplementation();
@@ -108,7 +126,7 @@
         // We can't initialize the implementation. This might be because
         // it's been renamed or no longer exists.
         $item = id(new PHUIObjectItemView())
-          ->setObjectName(pht('Step %d', $i++))
+          ->setObjectName(pht('Step %d.%d', $depth, $i))
           ->setHeader(pht('Unknown Implementation'))
           ->setBarColor('red')
           ->addAttribute(pht(
@@ -127,7 +145,7 @@
         continue;
       }
       $item = id(new PHUIObjectItemView())
-        ->setObjectName('Step '.$i++)
+        ->setObjectName(pht('Step %d.%d', $depth, $i))
         ->setHeader($step->getName());
 
       $item->addAttribute($implementation->getDescription());
@@ -138,12 +156,6 @@
 
       if ($can_edit) {
         $item->setHref($edit_uri);
-        $item->setGrippable(true);
-        $item->addSigil('build-step');
-        $item->setMetadata(
-          array(
-            'stepID' => $step->getID(),
-          ));
       }
 
       $item
@@ -157,17 +169,23 @@
             ->setHref(
               $this->getApplicationURI('step/delete/'.$step->getID().'/')));
 
+      $depends = $step->getStepImplementation()->getDependencies($step);
       $inputs = $step->getStepImplementation()->getArtifactInputs();
       $outputs = $step->getStepImplementation()->getArtifactOutputs();
 
       $has_conflicts = false;
-      if ($inputs || $outputs) {
+      if ($depends || $inputs || $outputs) {
         $available_artifacts =
-          HarbormasterBuildStepImplementation::loadAvailableArtifacts(
+          HarbormasterBuildStepImplementation::getAvailableArtifacts(
             $plan,
             $step,
             null);
 
+        list($depends_ui, $has_conflicts) = $this->buildDependsOnList(
+            $depends,
+            pht('Depends On'),
+            $steps);
+
         list($inputs_ui, $has_conflicts) = $this->buildArtifactList(
             $inputs,
             'in',
@@ -187,6 +205,7 @@
               'class' => 'harbormaster-artifact-io',
             ),
             array(
+              $depends_ui,
               $inputs_ui,
               $outputs_ui,
             )));
@@ -197,10 +216,18 @@
         $item->setBarColor('red');
       }
 
+      if ($run_ref['cycle']) {
+        $is_deadlocking = true;
+      }
+
+      if ($is_deadlocking) {
+        $item->setBarColor('red');
+      }
+
       $step_list->addItem($item);
     }
 
-    return array($step_list, $has_any_conflicts);
+    return array($step_list, $has_any_conflicts, $is_deadlocking);
   }
 
   private function buildActionList(HarbormasterBuildPlan $plan) {
@@ -291,7 +318,6 @@
       return array(null, $has_conflicts);
     }
 
-
     $this->requireResource('harbormaster-css');
 
     $header = phutil_tag(
@@ -384,4 +410,69 @@
     return array($ui, $has_conflicts);
   }
 
+  private function buildDependsOnList(
+    array $step_phids,
+    $name,
+    array $steps) {
+    $has_conflicts = false;
+
+    if (count($step_phids) === 0) {
+      return null;
+    }
+
+    $this->requireResource('harbormaster-css');
+
+    $steps = mpull($steps, null, 'getPHID');
+
+    $header = phutil_tag(
+      'div',
+      array(
+        'class' => 'harbormaster-artifact-summary-header',
+      ),
+      $name);
+
+    $list = new PHUIStatusListView();
+    foreach ($step_phids as $step_phid) {
+      $error = null;
+
+      if (idx($steps, $step_phid) === null) {
+        $icon = PHUIStatusItemView::ICON_WARNING;
+        $color = 'red';
+        $icon_label = pht('Missing Dependency');
+        $has_conflicts = true;
+        $error = pht(
+          'This dependency specifies a build step which doesn\'t exist.');
+      } else {
+        $bound = phutil_tag(
+          'strong',
+          array(),
+          idx($steps, $step_phid)->getName());
+        $icon = PHUIStatusItemView::ICON_ACCEPT;
+        $color = 'green';
+        $icon_label = pht('Valid Input');
+      }
+
+      if ($error) {
+        $note = array(
+          phutil_tag('strong', array(), pht('ERROR:')),
+          ' ',
+          $error);
+      } else {
+        $note = $bound;
+      }
+
+      $list->addItem(
+        id(new PHUIStatusItemView())
+          ->setIcon($icon, $color, $icon_label)
+          ->setTarget(pht('Build Step'))
+          ->setNote($note));
+    }
+
+    $ui = array(
+      $header,
+      $list,
+    );
+
+    return array($ui, $has_conflicts);
+  }
 }
diff --git a/src/applications/harbormaster/controller/HarbormasterStepEditController.php b/src/applications/harbormaster/controller/HarbormasterStepEditController.php
--- a/src/applications/harbormaster/controller/HarbormasterStepEditController.php
+++ b/src/applications/harbormaster/controller/HarbormasterStepEditController.php
@@ -65,12 +65,21 @@
 
     $e_name = true;
     $v_name = $step->getName();
+    $e_depends_on = true;
+    $raw_depends_on = $step->getDetail('dependsOn', array());
+
+    $v_depends_on = id(new PhabricatorHandleQuery())
+      ->setViewer($viewer)
+      ->withPHIDs($raw_depends_on)
+      ->execute();
 
     $errors = array();
     $validation_exception = null;
     if ($request->isFormPost()) {
       $e_name = null;
       $v_name = $request->getStr('name');
+      $e_depends_on = null;
+      $v_depends_on = $request->getArr('dependsOn');
 
       $xactions = $field_list->buildFieldTransactionsFromRequest(
         new HarbormasterBuildStepTransaction(),
@@ -86,12 +95,13 @@
         ->setNewValue($v_name);
       array_unshift($xactions, $name_xaction);
 
-      if ($is_new) {
-        // This is okay, but a little iffy. We should move it inside the editor
-        // if we create plans elsewhere.
-        $steps = $plan->loadOrderedBuildSteps();
-        $step->setSequence(count($steps) + 1);
+      $depends_on_xaction = id(new HarbormasterBuildStepTransaction())
+        ->setTransactionType(
+          HarbormasterBuildStepTransaction::TYPE_DEPENDS_ON)
+        ->setNewValue($v_depends_on);
+      array_unshift($xactions, $depends_on_xaction);
 
+      if ($is_new) {
         // When creating a new step, make sure we have a create transaction
         // so we'll apply the transactions even if the step has no
         // configurable options.
@@ -117,6 +127,19 @@
           ->setError($e_name)
           ->setValue($v_name));
 
+    $form
+      ->appendChild(
+        id(new AphrontFormTokenizerControl())
+          ->setDatasource(id(new HarbormasterBuildDependencyDatasource())
+            ->setParameters(array(
+              'planPHID' => $plan->getPHID(),
+              'stepPHID' => $is_new ? null : $step->getPHID(),
+            )))
+          ->setName('dependsOn')
+          ->setLabel(pht('Depends On'))
+          ->setError($e_depends_on)
+          ->setValue($v_depends_on));
+
     $field_list->appendFieldsToForm($form);
 
     if ($is_new) {
diff --git a/src/applications/harbormaster/editor/HarbormasterBuildStepEditor.php b/src/applications/harbormaster/editor/HarbormasterBuildStepEditor.php
--- a/src/applications/harbormaster/editor/HarbormasterBuildStepEditor.php
+++ b/src/applications/harbormaster/editor/HarbormasterBuildStepEditor.php
@@ -8,6 +8,7 @@
 
     $types[] = HarbormasterBuildStepTransaction::TYPE_CREATE;
     $types[] = HarbormasterBuildStepTransaction::TYPE_NAME;
+    $types[] = HarbormasterBuildStepTransaction::TYPE_DEPENDS_ON;
 
     return $types;
   }
@@ -24,6 +25,11 @@
           return null;
         }
         return $object->getName();
+      case HarbormasterBuildStepTransaction::TYPE_DEPENDS_ON:
+        if ($this->getIsNewObject()) {
+          return null;
+        }
+        return $object->getDetail('dependsOn', array());
     }
 
     return parent::getCustomTransactionOldValue($object, $xaction);
@@ -37,6 +43,7 @@
       case HarbormasterBuildStepTransaction::TYPE_CREATE:
         return true;
       case HarbormasterBuildStepTransaction::TYPE_NAME:
+      case HarbormasterBuildStepTransaction::TYPE_DEPENDS_ON:
         return $xaction->getNewValue();
     }
 
@@ -52,6 +59,8 @@
         return;
       case HarbormasterBuildStepTransaction::TYPE_NAME:
         return $object->setName($xaction->getNewValue());
+      case HarbormasterBuildStepTransaction::TYPE_DEPENDS_ON:
+        return $object->setDetail('dependsOn', $xaction->getNewValue());
     }
 
     return parent::applyCustomInternalTransaction($object, $xaction);
@@ -64,6 +73,7 @@
     switch ($xaction->getTransactionType()) {
       case HarbormasterBuildStepTransaction::TYPE_CREATE:
       case HarbormasterBuildStepTransaction::TYPE_NAME:
+      case HarbormasterBuildStepTransaction::TYPE_DEPENDS_ON:
         return;
     }
 
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
@@ -246,22 +246,14 @@
     // Identify all the steps which are ready to run (because all their
     // dependencies are complete).
 
-    $previous_step = null;
     $runnable = array();
     foreach ($steps as $step) {
-      // TODO: For now, we're hard coding sequential dependencies into build
-      // steps. In the future, we can be smart about this instead.
-
-      if ($previous_step) {
-        $dependencies = array($previous_step);
-      } else {
-        $dependencies = array();
-      }
+      $dependencies = $step->getStepImplementation()->getDependencies($step);
 
       if (isset($queued[$step->getPHID()])) {
         $can_run = true;
         foreach ($dependencies as $dependency) {
-          if (empty($complete[$dependency->getPHID()])) {
+          if (empty($complete[$dependency])) {
             $can_run = false;
             break;
           }
@@ -271,14 +263,12 @@
           $runnable[] = $step;
         }
       }
-
-      $previous_step = $step;
     }
 
     if (!$runnable && !$waiting && !$underway) {
-      // TODO: This means the build is deadlocked, probably? It should not
-      // normally be possible yet, but we should communicate it more clearly.
-      $build->setBuildStatus(HarbormasterBuild::STATUS_FAILED);
+      // This means the build is deadlocked, and the user has configured
+      // circular dependencies.
+      $build->setBuildStatus(HarbormasterBuild::STATUS_DEADLOCKED);
       $build->save();
       return;
     }
@@ -292,7 +282,6 @@
 
       $this->queueNewBuildTarget($target);
     }
-
   }
 
 
@@ -378,7 +367,8 @@
         $all_pass = false;
       }
       if ($build->getBuildStatus() == HarbormasterBuild::STATUS_FAILED ||
-          $build->getBuildStatus() == HarbormasterBuild::STATUS_ERROR) {
+          $build->getBuildStatus() == HarbormasterBuild::STATUS_ERROR ||
+          $build->getBuildStatus() == HarbormasterBuild::STATUS_DEADLOCKED) {
         $any_fail = true;
       }
     }
diff --git a/src/applications/harbormaster/engine/HarbormasterBuildGraph.php b/src/applications/harbormaster/engine/HarbormasterBuildGraph.php
new file mode 100644
--- /dev/null
+++ b/src/applications/harbormaster/engine/HarbormasterBuildGraph.php
@@ -0,0 +1,60 @@
+<?php
+
+/**
+ * Directed graph representing a build plan
+ */
+final class HarbormasterBuildGraph extends AbstractDirectedGraph {
+
+  private $stepMap;
+
+  public static function determineDependencyExecution(
+    HarbormasterBuildPlan $plan) {
+
+    $steps = id(new HarbormasterBuildStepQuery())
+      ->setViewer(PhabricatorUser::getOmnipotentUser())
+      ->withBuildPlanPHIDs(array($plan->getPHID()))
+      ->execute();
+
+    $steps_by_phid = mpull($steps, null, 'getPHID');
+    $step_phids = mpull($steps, 'getPHID');
+
+    if (count($steps) === 0) {
+      return array();
+    }
+
+    $graph = id(new HarbormasterBuildGraph($steps_by_phid))
+      ->addNodes($step_phids);
+
+    $raw_results =
+      $graph->getBestEffortTopographicallySortedNodes();
+
+    $results = array();
+    foreach ($raw_results as $node) {
+      $results[] = array(
+        'node' => $steps_by_phid[$node['node']],
+        'depth' => $node['depth'],
+        'cycle' => $node['cycle']);
+    }
+
+    return $results;
+  }
+
+  public function __construct($step_map) {
+    $this->stepMap = $step_map;
+  }
+
+  protected function loadEdges(array $nodes) {
+    $map = array();
+    foreach ($nodes as $node) {
+      $deps = $this->stepMap[$node]->getDetail('dependsOn', array());
+
+      $map[$node] = array();
+      foreach ($deps as $dep) {
+        $map[$node][] = $dep;
+      }
+    }
+
+    return $map;
+  }
+
+}
diff --git a/src/applications/harbormaster/phid/HarbormasterBuildStepPHIDType.php b/src/applications/harbormaster/phid/HarbormasterBuildStepPHIDType.php
--- a/src/applications/harbormaster/phid/HarbormasterBuildStepPHIDType.php
+++ b/src/applications/harbormaster/phid/HarbormasterBuildStepPHIDType.php
@@ -27,6 +27,10 @@
 
     foreach ($handles as $phid => $handle) {
       $build_step = $objects[$phid];
+
+      $name = $build_step->getName();
+
+      $handle->setName($name);
     }
   }
 
diff --git a/src/applications/harbormaster/query/HarbormasterBuildStepQuery.php b/src/applications/harbormaster/query/HarbormasterBuildStepQuery.php
--- a/src/applications/harbormaster/query/HarbormasterBuildStepQuery.php
+++ b/src/applications/harbormaster/query/HarbormasterBuildStepQuery.php
@@ -22,14 +22,6 @@
     return $this;
   }
 
-  public function getPagingColumn() {
-    return 'sequence';
-  }
-
-  public function getReversePaging() {
-    return true;
-  }
-
   protected function loadPage() {
     $table = new HarbormasterBuildStep();
     $conn_r = $table->establishConnection('r');
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
@@ -98,41 +98,35 @@
     return array();
   }
 
-  /**
-   * Returns a list of all artifacts made available by previous build steps.
-   */
-  public static function loadAvailableArtifacts(
-    HarbormasterBuildPlan $build_plan,
-    HarbormasterBuildStep $current_build_step,
-    $artifact_type) {
-
-    $build_steps = $build_plan->loadOrderedBuildSteps();
-
-    return self::getAvailableArtifacts(
-      $build_plan,
-      $build_steps,
-      $current_build_step,
-      $artifact_type);
+  public function getDependencies(HarbormasterBuildStep $build_step) {
+    return $build_step->getDetail('dependsOn', array());
   }
 
   /**
-   * Returns a list of all artifacts made available by previous build steps.
+   * Returns a list of all artifacts made available in the build plan.
    */
   public static function getAvailableArtifacts(
     HarbormasterBuildPlan $build_plan,
-    array $build_steps,
-    HarbormasterBuildStep $current_build_step,
+    $current_build_step,
     $artifact_type) {
 
-    $previous_implementations = array();
-    foreach ($build_steps as $build_step) {
-      if ($build_step->getPHID() === $current_build_step->getPHID()) {
-        break;
+    $steps = id(new HarbormasterBuildStepQuery())
+      ->setViewer(PhabricatorUser::getOmnipotentUser())
+      ->withBuildPlanPHIDs(array($build_plan->getPHID()))
+      ->execute();
+
+    $artifact_arrays = array();
+    foreach ($steps as $step) {
+      if ($current_build_step !== null &&
+        $step->getPHID() === $current_build_step->getPHID()) {
+
+        continue;
       }
-      $previous_implementations[] = $build_step->getStepImplementation();
+
+      $implementation = $step->getStepImplementation();
+      $artifact_arrays[] = $implementation->getArtifactOutputs();
     }
 
-    $artifact_arrays = mpull($previous_implementations, 'getArtifactOutputs');
     $artifacts = array();
     foreach ($artifact_arrays as $array) {
       $array = ipull($array, 'type', 'key');
diff --git a/src/applications/harbormaster/storage/build/HarbormasterBuild.php b/src/applications/harbormaster/storage/build/HarbormasterBuild.php
--- a/src/applications/harbormaster/storage/build/HarbormasterBuild.php
+++ b/src/applications/harbormaster/storage/build/HarbormasterBuild.php
@@ -47,6 +47,11 @@
    */
   const STATUS_STOPPED = 'stopped';
 
+  /**
+   * The build has been deadlocked.
+   */
+  const STATUS_DEADLOCKED = 'deadlocked';
+
 
   /**
    * Get a human readable name for a build status constant.
@@ -70,6 +75,8 @@
         return pht('Unexpected Error');
       case self::STATUS_STOPPED:
         return pht('Stopped');
+      case self::STATUS_DEADLOCKED:
+        return pht('Deadlocked');
       default:
         return pht('Unknown');
     }
@@ -90,6 +97,8 @@
         return PHUIStatusItemView::ICON_MINUS;
       case self::STATUS_STOPPED:
         return PHUIStatusItemView::ICON_MINUS;
+      case self::STATUS_DEADLOCKED:
+        return PHUIStatusItemView::ICON_WARNING;
       default:
         return PHUIStatusItemView::ICON_QUESTION;
     }
@@ -106,6 +115,7 @@
         return 'green';
       case self::STATUS_FAILED:
       case self::STATUS_ERROR:
+      case self::STATUS_DEADLOCKED:
         return 'red';
       case self::STATUS_STOPPED:
         return 'dark';
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
@@ -13,6 +13,7 @@
 
   const TYPE_FILE = 'file';
   const TYPE_HOST = 'host';
+  const TYPE_BUILD_STATE = 'buildstate';
 
   public static function initializeNewBuildArtifact(
     HarbormasterBuildTarget $build_target) {
diff --git a/src/applications/harbormaster/storage/configuration/HarbormasterBuildPlan.php b/src/applications/harbormaster/storage/configuration/HarbormasterBuildPlan.php
--- a/src/applications/harbormaster/storage/configuration/HarbormasterBuildPlan.php
+++ b/src/applications/harbormaster/storage/configuration/HarbormasterBuildPlan.php
@@ -39,19 +39,6 @@
     return $this->assertAttached($this->buildSteps);
   }
 
-  /**
-   * Returns a standard, ordered list of build steps for this build plan.
-   *
-   * This method should be used to load build steps for a given build plan
-   * so that the ordering is consistent.
-   */
-  public function loadOrderedBuildSteps() {
-    return id(new HarbormasterBuildStepQuery())
-      ->setViewer(PhabricatorUser::getOmnipotentUser())
-      ->withBuildPlanPHIDs(array($this->getPHID()))
-      ->execute();
-  }
-
   public function isDisabled() {
     return ($this->getPlanStatus() == self::STATUS_DISABLED);
   }
diff --git a/src/applications/harbormaster/storage/configuration/HarbormasterBuildStep.php b/src/applications/harbormaster/storage/configuration/HarbormasterBuildStep.php
--- a/src/applications/harbormaster/storage/configuration/HarbormasterBuildStep.php
+++ b/src/applications/harbormaster/storage/configuration/HarbormasterBuildStep.php
@@ -9,7 +9,7 @@
   protected $buildPlanPHID;
   protected $className;
   protected $details = array();
-  protected $sequence;
+  protected $sequence = 0;
 
   private $buildPlan = self::ATTACHABLE;
   private $customFields = self::ATTACHABLE;
diff --git a/src/applications/harbormaster/storage/configuration/HarbormasterBuildStepTransaction.php b/src/applications/harbormaster/storage/configuration/HarbormasterBuildStepTransaction.php
--- a/src/applications/harbormaster/storage/configuration/HarbormasterBuildStepTransaction.php
+++ b/src/applications/harbormaster/storage/configuration/HarbormasterBuildStepTransaction.php
@@ -5,6 +5,7 @@
 
   const TYPE_CREATE = 'harbormaster:step:create';
   const TYPE_NAME = 'harbormaster:step:name';
+  const TYPE_DEPENDS_ON = 'harbormaster:step:depends';
 
   public function getApplicationName() {
     return 'harbormaster';
diff --git a/src/applications/harbormaster/typeahead/HarbormasterBuildDependencyDatasource.php b/src/applications/harbormaster/typeahead/HarbormasterBuildDependencyDatasource.php
new file mode 100644
--- /dev/null
+++ b/src/applications/harbormaster/typeahead/HarbormasterBuildDependencyDatasource.php
@@ -0,0 +1,45 @@
+<?php
+
+final class HarbormasterBuildDependencyDatasource
+  extends PhabricatorTypeaheadDatasource {
+
+  public function getPlaceholderText() {
+    return pht('Type another build step name...');
+  }
+
+  public function getDatasourceApplicationClass() {
+    return 'PhabricatorHarbormasterApplication';
+  }
+
+  public function loadResults() {
+    $viewer = $this->getViewer();
+
+    $plan_phid = $this->getParameter('planPHID');
+    $step_phid = $this->getParameter('stepPHID');
+
+    $steps = id(new HarbormasterBuildStepQuery())
+      ->setViewer($viewer)
+      ->withBuildPlanPHIDs(array($plan_phid))
+      ->execute();
+    $steps = mpull($steps, null, 'getPHID');
+
+    if (count($steps) === 0) {
+      return array();
+    }
+
+    $results = array();
+    foreach ($steps as $phid => $step) {
+      if ($step->getPHID() === $step_phid) {
+        continue;
+      }
+
+      $results[] = id(new PhabricatorTypeaheadResult())
+        ->setName($step->getName())
+        ->setURI('/')
+        ->setPHID($phid);
+    }
+
+    return $results;
+  }
+
+}
diff --git a/src/applications/typeahead/controller/PhabricatorTypeaheadModularDatasourceController.php b/src/applications/typeahead/controller/PhabricatorTypeaheadModularDatasourceController.php
--- a/src/applications/typeahead/controller/PhabricatorTypeaheadModularDatasourceController.php
+++ b/src/applications/typeahead/controller/PhabricatorTypeaheadModularDatasourceController.php
@@ -30,6 +30,7 @@
 
     if (isset($sources[$this->class])) {
       $source = $sources[$this->class];
+      $source->setParameters($request->getRequestData());
 
       $composite = new PhabricatorTypeaheadRuntimeCompositeDatasource();
       $composite->addDatasource($source);
diff --git a/src/applications/typeahead/datasource/PhabricatorTypeaheadDatasource.php b/src/applications/typeahead/datasource/PhabricatorTypeaheadDatasource.php
--- a/src/applications/typeahead/datasource/PhabricatorTypeaheadDatasource.php
+++ b/src/applications/typeahead/datasource/PhabricatorTypeaheadDatasource.php
@@ -6,6 +6,7 @@
   private $query;
   private $rawQuery;
   private $limit;
+  private $parameters = array();
 
   public function setLimit($limit) {
     $this->limit = $limit;
@@ -43,8 +44,23 @@
     return $this->query;
   }
 
+  public function setParameters(array $params) {
+    $this->parameters = $params;
+    return $this;
+  }
+
+  public function getParameters() {
+    return $this->parameters;
+  }
+
+  public function getParameter($name, $default = null) {
+    return idx($this->parameters, $name, $default);
+  }
+
   public function getDatasourceURI() {
-    return '/typeahead/class/'.get_class($this).'/';
+    $uri = new PhutilURI('/typeahead/class/'.get_class($this).'/');
+    $uri->setQueryParams($this->parameters);
+    return (string)$uri;
   }
 
   abstract public function getPlaceholderText();
diff --git a/webroot/rsrc/js/application/harbormaster/behavior-reorder-steps.js b/webroot/rsrc/js/application/harbormaster/behavior-reorder-steps.js
deleted file mode 100644
--- a/webroot/rsrc/js/application/harbormaster/behavior-reorder-steps.js
+++ /dev/null
@@ -1,41 +0,0 @@
-/**
- * @provides javelin-behavior-harbormaster-reorder-steps
- * @requires javelin-behavior
- *           javelin-stratcom
- *           javelin-workflow
- *           javelin-dom
- *           phabricator-draggable-list
- */
-
-JX.behavior('harbormaster-reorder-steps', function(config) {
-
-  var root = JX.$(config.listID);
-
-  var list = new JX.DraggableList('build-step', root)
-    .setFindItemsHandler(function() {
-      return JX.DOM.scry(root, 'li', 'build-step');
-    });
-
-  list.listen('didDrop', function(node) {
-    var nodes = list.findItems();
-    var order = [];
-    var key;
-    for (var ii = 0; ii < nodes.length; ii++) {
-      key = JX.Stratcom.getData(nodes[ii]).stepID;
-      if (key) {
-        order.push(key);
-      }
-    }
-
-    list.lock();
-    JX.DOM.alterClass(node, 'drag-sending', true);
-
-    new JX.Workflow(config.orderURI, {order: order.join()})
-      .setHandler(function() {
-        JX.DOM.alterClass(node, 'drag-sending', false);
-        list.unlock();
-      })
-      .start();
-  });
-
-});