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
@@ -815,6 +815,9 @@
     'DiffusionGitUploadPackSSHWorkflow' => 'applications/diffusion/ssh/DiffusionGitUploadPackSSHWorkflow.php',
     'DiffusionGitUploadPackWireProtocol' => 'applications/diffusion/protocol/DiffusionGitUploadPackWireProtocol.php',
     'DiffusionGitWireProtocol' => 'applications/diffusion/protocol/DiffusionGitWireProtocol.php',
+    'DiffusionGitWireProtocolCapabilities' => 'applications/diffusion/protocol/DiffusionGitWireProtocolCapabilities.php',
+    'DiffusionGitWireProtocolRef' => 'applications/diffusion/protocol/DiffusionGitWireProtocolRef.php',
+    'DiffusionGitWireProtocolRefList' => 'applications/diffusion/protocol/DiffusionGitWireProtocolRefList.php',
     'DiffusionGraphController' => 'applications/diffusion/controller/DiffusionGraphController.php',
     'DiffusionHistoryController' => 'applications/diffusion/controller/DiffusionHistoryController.php',
     'DiffusionHistoryListView' => 'applications/diffusion/view/DiffusionHistoryListView.php',
@@ -6464,6 +6467,9 @@
     'DiffusionGitUploadPackSSHWorkflow' => 'DiffusionGitSSHWorkflow',
     'DiffusionGitUploadPackWireProtocol' => 'DiffusionGitWireProtocol',
     'DiffusionGitWireProtocol' => 'Phobject',
+    'DiffusionGitWireProtocolCapabilities' => 'Phobject',
+    'DiffusionGitWireProtocolRef' => 'Phobject',
+    'DiffusionGitWireProtocolRefList' => 'Phobject',
     'DiffusionGraphController' => 'DiffusionController',
     'DiffusionHistoryController' => 'DiffusionController',
     'DiffusionHistoryListView' => 'DiffusionHistoryView',
diff --git a/src/applications/diffusion/protocol/DiffusionGitUploadPackWireProtocol.php b/src/applications/diffusion/protocol/DiffusionGitUploadPackWireProtocol.php
--- a/src/applications/diffusion/protocol/DiffusionGitUploadPackWireProtocol.php
+++ b/src/applications/diffusion/protocol/DiffusionGitUploadPackWireProtocol.php
@@ -166,13 +166,17 @@
     $head_key = head_key($frames);
     $last_key = last_key($frames);
 
-    $output = array();
+    $capabilities = null;
+    $last_frame = null;
+
+    $refs = array();
     foreach ($frames as $key => $frame) {
       $is_last = ($key === $last_key);
       if ($is_last) {
-        $output[] = $frame;
         // This is a "0000" frame at the end of the list of refs, so we pass
-        // it through unmodified.
+        // it through unmodified after we figure out what the rest of the
+        // frames should look like, below.
+        $last_frame = $frame;
         continue;
       }
 
@@ -230,42 +234,69 @@
 
       $hash = $matches['hash'];
       $name = $matches['name'];
-      $capabilities = idx($matches, 'capabilities');
 
-      $ref = array(
+      if ($is_first) {
+        $capabilities = $matches['capabilities'];
+      }
+
+      $refs[] = array(
         'hash' => $hash,
         'name' => $name,
-        'capabilities' => $capabilities,
       );
+    }
 
-      $old_ref = $ref;
+    $capabilities = DiffusionGitWireProtocolCapabilities::newFromWireFormat(
+      $capabilities);
 
-      $ref = $this->willReadRef($ref);
+    $ref_list = id(new DiffusionGitWireProtocolRefList())
+      ->setCapabilities($capabilities);
 
-      $new_ref = $ref;
+    foreach ($refs as $ref) {
+      $ref_list->addRef(
+        id(new DiffusionGitWireProtocolRef())
+          ->setName($ref['name'])
+          ->setHash($ref['hash']));
+    }
 
-      $this->didRewriteRef($old_ref, $new_ref);
+    // TODO: Here, we have a structured list of refs. In a future change,
+    // we are free to mutate the structure before flattening it back into
+    // wire format.
 
-      if ($ref === null) {
-        continue;
-      }
+    $refs = $ref_list->getRefs();
+
+    // Before we write the ref list, sort it for consistency with native
+    // Git output. We may have added, removed, or renamed refs and ended up
+    // with an out-of-order list.
+
+    $refs = msortv($refs, 'newSortVector');
+
+    // The first ref we send back includes the capabilities data. Note that if
+    // we send back no refs, we also don't send back capabilities! This is
+    // a little surprising, but is consistent with the native behavior of the
+    // protocol.
 
-      if (isset($ref['capabilities'])) {
+    $output = array();
+    $is_first = true;
+    foreach ($refs as $ref) {
+      if ($is_first) {
         $result = sprintf(
           "%s %s\0%s\n",
-          $ref['hash'],
-          $ref['name'],
-          $ref['capabilities']);
+          $ref->getHash(),
+          $ref->getName(),
+          $ref_list->getCapabilities()->toWireFormat());
       } else {
         $result = sprintf(
           "%s %s\n",
-          $ref['hash'],
-          $ref['name']);
+          $ref->getHash(),
+          $ref->getName());
       }
 
       $output[] = $this->newProtocolFrame('data', $result);
+      $is_first = false;
     }
 
+    $output[] = $last_frame;
+
     return $this->newProtocolDataMessage($output);
   }
 
@@ -291,45 +322,4 @@
     return $message;
   }
 
-  private function willReadRef(array $ref) {
-    return $ref;
-  }
-
-  private function didRewriteRef($old_ref, $new_ref) {
-    $log = $this->getProtocolLog();
-    if (!$log) {
-      return;
-    }
-
-    if (!$old_ref) {
-      $old_name = null;
-    } else {
-      $old_name = $old_ref['name'];
-    }
-
-    if (!$new_ref) {
-      $new_name = null;
-    } else {
-      $new_name = $new_ref['name'];
-    }
-
-    if ($old_name === $new_name) {
-      return;
-    }
-
-    if ($old_name === null) {
-      $old_name = '<null>';
-    }
-
-    if ($new_name === null) {
-      $new_name = '<null>';
-    }
-
-    $log->didWriteFrame(
-      pht(
-        'Rewrite Ref: %s -> %s',
-        $old_name,
-        $new_name));
-  }
-
 }
diff --git a/src/applications/diffusion/protocol/DiffusionGitWireProtocolCapabilities.php b/src/applications/diffusion/protocol/DiffusionGitWireProtocolCapabilities.php
new file mode 100644
--- /dev/null
+++ b/src/applications/diffusion/protocol/DiffusionGitWireProtocolCapabilities.php
@@ -0,0 +1,18 @@
+<?php
+
+final class DiffusionGitWireProtocolCapabilities
+  extends Phobject {
+
+  private $raw;
+
+  public static function newFromWireFormat($raw) {
+    $capabilities = new self();
+    $capabilities->raw = $raw;
+    return $capabilities;
+  }
+
+  public function toWireFormat() {
+    return $this->raw;
+  }
+
+}
diff --git a/src/applications/diffusion/protocol/DiffusionGitWireProtocolRef.php b/src/applications/diffusion/protocol/DiffusionGitWireProtocolRef.php
new file mode 100644
--- /dev/null
+++ b/src/applications/diffusion/protocol/DiffusionGitWireProtocolRef.php
@@ -0,0 +1,32 @@
+<?php
+
+final class DiffusionGitWireProtocolRef
+  extends Phobject {
+
+  private $name;
+  private $hash;
+
+  public function setName($name) {
+    $this->name = $name;
+    return $this;
+  }
+
+  public function getName() {
+    return $this->name;
+  }
+
+  public function setHash($hash) {
+    $this->hash = $hash;
+    return $this;
+  }
+
+  public function getHash() {
+    return $this->hash;
+  }
+
+  public function newSortVector() {
+    return id(new PhutilSortVector())
+      ->addString($this->getName());
+  }
+
+}
diff --git a/src/applications/diffusion/protocol/DiffusionGitWireProtocolRefList.php b/src/applications/diffusion/protocol/DiffusionGitWireProtocolRefList.php
new file mode 100644
--- /dev/null
+++ b/src/applications/diffusion/protocol/DiffusionGitWireProtocolRefList.php
@@ -0,0 +1,28 @@
+<?php
+
+final class DiffusionGitWireProtocolRefList
+  extends Phobject {
+
+  private $capabilities;
+  private $refs = array();
+
+  public function setCapabilities(
+    DiffusionGitWireProtocolCapabilities $capabilities) {
+    $this->capabilities = $capabilities;
+    return $this;
+  }
+
+  public function getCapabilities() {
+    return $this->capabilities;
+  }
+
+  public function addRef(DiffusionGitWireProtocolRef $ref) {
+    $this->refs[] = $ref;
+    return $this;
+  }
+
+  public function getRefs() {
+    return $this->refs;
+  }
+
+}