Index: src/applications/project/controller/PhabricatorProjectBoardController.php
===================================================================
--- src/applications/project/controller/PhabricatorProjectBoardController.php
+++ src/applications/project/controller/PhabricatorProjectBoardController.php
@@ -54,11 +54,23 @@
       ->execute();
     $tasks = mpull($tasks, null, 'getPHID');
 
+    $edge_type = PhabricatorEdgeConfig::TYPE_OBJECT_HAS_COLUMN;
+    $edge_query = id(new PhabricatorEdgeQuery())
+      ->withSourcePHIDs(mpull($tasks, 'getPHID'))
+      ->withEdgeTypes(array($edge_type))
+      ->withDestinationPHIDs(mpull($columns, 'getPHID'));
+    $edge_query->execute();
+
     $task_map = array();
     $default_phid = $columns[0]->getPHID();
-
     foreach ($tasks as $task) {
-      $task_map[$default_phid][] = $task->getPHID();
+      $task_phid = $task->getPHID();
+      $column_phids = $edge_query->getDestinationPHIDs(array($task_phid));
+
+      $column_phid = head($column_phids);
+      $column_phid = nonempty($column_phid, $default_phid);
+
+      $task_map[$column_phid][] = $task_phid;
     }
 
     $board_id = celerity_generate_unique_node_id();
Index: src/applications/project/controller/PhabricatorProjectMoveController.php
===================================================================
--- src/applications/project/controller/PhabricatorProjectMoveController.php
+++ src/applications/project/controller/PhabricatorProjectMoveController.php
@@ -13,6 +13,10 @@
     $request = $this->getRequest();
     $viewer = $request->getUser();
 
+    $column_phid = $request->getStr('columnPHID');
+    $object_phid = $request->getStr('objectPHID');
+    $after_phid = $request->getStr('afterPHID');
+
     $project = id(new PhabricatorProjectQuery())
       ->setViewer($viewer)
       ->requireCapabilities(
@@ -26,6 +30,91 @@
       return new Aphront404Response();
     }
 
+    // NOTE: I'm not requiring EDIT on the object for now, since we require
+    // EDIT on the project anyway and this relationship is more owned by the
+    // project than the object. Maybe this is worth revisiting eventually.
+
+    $object = id(new PhabricatorObjectQuery())
+      ->setViewer($viewer)
+      ->withPHIDs(array($object_phid))
+      ->executeOne();
+
+    if (!$object) {
+      return new Aphront404Response();
+    }
+
+    $columns = id(new PhabricatorProjectColumnQuery())
+      ->setViewer($viewer)
+      ->withProjectPHIDs(array($project->getPHID()))
+      ->execute();
+
+    $columns = mpull($columns, null, 'getPHID');
+    if (empty($columns[$column_phid])) {
+      // User is trying to drop this object into a nonexistent column, just kick
+      // them out.
+      return new Aphront404Response();
+    }
+
+    $edge_type = PhabricatorEdgeConfig::TYPE_OBJECT_HAS_COLUMN;
+
+    $query = id(new PhabricatorEdgeQuery())
+      ->withSourcePHIDs(array($object->getPHID()))
+      ->withEdgeTypes(array($edge_type))
+      ->withDestinationPHIDs(array_keys($columns));
+
+    $query->execute();
+
+    $edge_phids = $query->getDestinationPHIDs();
+
+    $this->rewriteEdges(
+      $object->getPHID(),
+      $edge_type,
+      $column_phid,
+      $edge_phids);
+
+    // TODO: We also need to deal with priorities, so far this only gets stuff
+    // in the correct column.
+
     return id(new AphrontAjaxResponse())->setContent(array());
   }
+
+  private function rewriteEdges($src, $edge_type, $dst, array $edges) {
+    $viewer = $this->getRequest()->getUser();
+
+    // NOTE: Normally, we expect only one edge to exist, but this works in a
+    // general way so it will repair any stray edges.
+
+    $remove = array();
+    $edge_missing = true;
+    foreach ($edges as $phid) {
+      if ($phid == $dst) {
+        $edge_missing = false;
+      } else {
+        $remove[] = $phid;
+      }
+    }
+
+    $add = array();
+    if ($edge_missing) {
+      $add[] = $dst;
+    }
+
+    if (!$add && !$remove) {
+      return;
+    }
+
+    $editor = id(new PhabricatorEdgeEditor())
+      ->setActor($viewer)
+      ->setSuppressEvents(true);
+
+    foreach ($add as $phid) {
+      $editor->addEdge($src, $edge_type, $phid);
+    }
+    foreach ($remove as $phid) {
+      $editor->removeEdge($src, $edge_type, $phid);
+    }
+
+    $editor->save();
+  }
+
 }
Index: src/infrastructure/edges/constants/PhabricatorEdgeConfig.php
===================================================================
--- src/infrastructure/edges/constants/PhabricatorEdgeConfig.php
+++ src/infrastructure/edges/constants/PhabricatorEdgeConfig.php
@@ -66,6 +66,9 @@
   const TYPE_OBJECT_HAS_PROJECT         = 41;
   const TYPE_PROJECT_HAS_OBJECT         = 42;
 
+  const TYPE_OBJECT_HAS_COLUMN          = 43;
+  const TYPE_COLUMN_HAS_OBJECT          = 44;
+
   const TYPE_TEST_NO_CYCLE              = 9000;
 
   const TYPE_PHOB_HAS_ASANATASK         = 80001;
@@ -77,7 +80,6 @@
   const TYPE_PHOB_HAS_JIRAISSUE         = 80004;
   const TYPE_JIRAISSUE_HAS_PHOB         = 80005;
 
-
   public static function getInverse($edge_type) {
     static $map = array(
       self::TYPE_TASK_HAS_COMMIT => self::TYPE_COMMIT_HAS_TASK,
@@ -148,6 +150,9 @@
 
       self::TYPE_OBJECT_HAS_PROJECT => self::TYPE_PROJECT_HAS_OBJECT,
       self::TYPE_PROJECT_HAS_OBJECT => self::TYPE_OBJECT_HAS_PROJECT,
+
+      self::TYPE_OBJECT_HAS_COLUMN => self::TYPE_COLUMN_HAS_OBJECT,
+      self::TYPE_COLUMN_HAS_OBJECT => self::TYPE_OBJECT_HAS_COLUMN,
     );
 
     return idx($map, $edge_type);