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
@@ -103,6 +103,7 @@
   private function updateBuild(HarbormasterBuild $build) {
     if ($build->isAborting()) {
       $this->releaseAllArtifacts($build);
+      $this->abortWaitingSteps($build);
       $build->setBuildStatus(HarbormasterBuild::STATUS_ABORTED);
       $build->save();
     }
@@ -293,6 +294,37 @@
     }
   }
 
+  private function abortWaitingSteps(HarbormasterBuild $build) {
+    $targets = id(new HarbormasterBuildTargetQuery())
+      ->setViewer($this->getViewer())
+      ->withBuildPHIDs(array($build->getPHID()))
+      ->withBuildGenerations(array($build->getBuildGeneration()))
+      ->execute();
+
+    $targets = mgroup($targets, 'getBuildStepPHID');
+
+    $steps = id(new HarbormasterBuildStepQuery())
+      ->setViewer($this->getViewer())
+      ->withBuildPlanPHIDs(array($build->getBuildPlan()->getPHID()))
+      ->execute();
+
+    foreach ($steps as $step) {
+      $step_targets = idx($targets, $step->getPHID(), array());
+
+      foreach ($step_targets as $target) {
+        if ($target->isWaiting()) {
+          try {
+            $step->abortWaitingForMessage();
+          } catch (Exception $ex) {
+            // TODO ?
+            // We're already aborting, but we should try to stop all steps
+          }
+          break;
+        }
+      }
+    }
+  }
+
 
   /**
    * Process messages which were sent to these targets, kicking applicable
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
@@ -245,6 +245,11 @@
     return (bool)$target->getDetail('builtin.wait-for-message');
   }
 
+  public function abortWaitingForMessage() {
+    // Normally do nothing. Steps that are run remotely might want to instruct
+    // the remote service to abort.
+  }
+
   protected function shouldAbort(
     HarbormasterBuild $build,
     HarbormasterBuildTarget $target) {