diff --git a/src/applications/project/engine/PhabricatorBoardLayoutEngine.php b/src/applications/project/engine/PhabricatorBoardLayoutEngine.php
--- a/src/applications/project/engine/PhabricatorBoardLayoutEngine.php
+++ b/src/applications/project/engine/PhabricatorBoardLayoutEngine.php
@@ -229,7 +229,7 @@
     $this->addQueue[] = $object_position;
 
     $positions[$object_phid] = $object_position;
-    $positions = msort($positions, 'getOrderingKey');
+    $positions = msortv($positions, 'newColumnPositionOrderVector');
 
     $this->boardLayout[$board_phid][$column_phid] = $positions;
 
@@ -404,7 +404,7 @@
       ->withBoardPHIDs(array_keys($boards))
       ->withObjectPHIDs($object_phids)
       ->execute();
-    $positions = msort($positions, 'getOrderingKey');
+    $positions = msortv($positions, 'newColumnPositionOrderVector');
     $positions = mgroup($positions, 'getBoardPHID');
 
     return $positions;
@@ -581,7 +581,7 @@
     }
 
     foreach ($layout as $column_phid => $map) {
-      $map = msort($map, 'getOrderingKey');
+      $map = msortv($map, 'newColumnPositionOrderVector');
       $layout[$column_phid] = $map;
 
       foreach ($map as $object_phid => $position) {
diff --git a/src/applications/project/engine/PhabricatorBoardResponseEngine.php b/src/applications/project/engine/PhabricatorBoardResponseEngine.php
--- a/src/applications/project/engine/PhabricatorBoardResponseEngine.php
+++ b/src/applications/project/engine/PhabricatorBoardResponseEngine.php
@@ -100,10 +100,17 @@
       $all_objects = mpull($all_objects, null, 'getPHID');
     }
 
+    // NOTE: The board layout engine is sensitive to PHID input order, and uses
+    // the input order as a component of the "natural" column ordering if no
+    // explicit ordering is specified. Rearrange the PHIDs in ID order.
+
+    $all_objects = msort($all_objects, 'getID');
+    $ordered_phids = mpull($all_objects, 'getPHID');
+
     $layout_engine = id(new PhabricatorBoardLayoutEngine())
       ->setViewer($viewer)
       ->setBoardPHIDs(array($board_phid))
-      ->setObjectPHIDs($all_phids)
+      ->setObjectPHIDs($ordered_phids)
       ->executeLayout();
 
     $natural = array();
diff --git a/src/applications/project/storage/PhabricatorProjectColumnPosition.php b/src/applications/project/storage/PhabricatorProjectColumnPosition.php
--- a/src/applications/project/storage/PhabricatorProjectColumnPosition.php
+++ b/src/applications/project/storage/PhabricatorProjectColumnPosition.php
@@ -46,7 +46,7 @@
     return $this;
   }
 
-  public function getOrderingKey() {
+  public function newColumnPositionOrderVector() {
     // We're ordering both real positions and "virtual" positions which we have
     // created but not saved yet.
 
@@ -61,11 +61,10 @@
 
     // Broadly, this collectively makes newly added stuff float to the top.
 
-    return sprintf(
-      '~%012d%012d%012d',
-      $this->getSequence(),
-      ((1 << 31) - $this->viewSequence),
-      ((1 << 31) - $this->getID()));
+    return id(new PhutilSortVector())
+      ->addInt($this->getSequence())
+      ->addInt(-1 * $this->viewSequence)
+      ->addInt(-1 * $this->getID());
   }
 
 /* -(  PhabricatorPolicyInterface  )----------------------------------------- */