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
@@ -529,6 +529,7 @@
     'phlog' => 'error/phlog.php',
     'pht' => 'internationalization/pht.php',
     'phutil_build_http_querystring' => 'utils/utils.php',
+    'phutil_build_http_querystring_from_pairs' => 'utils/utils.php',
     'phutil_censor_credentials' => 'utils/utils.php',
     'phutil_console_confirm' => 'console/format.php',
     'phutil_console_format' => 'console/format.php',
@@ -559,6 +560,7 @@
     'phutil_get_signal_name' => 'future/exec/execx.php',
     'phutil_get_system_locale' => 'utils/utf8.php',
     'phutil_hashes_are_identical' => 'utils/utils.php',
+    'phutil_http_parameter_pair' => 'utils/utils.php',
     'phutil_implode_html' => 'markup/render.php',
     'phutil_ini_decode' => 'utils/utils.php',
     'phutil_is_hiphop_runtime' => 'utils/utils.php',
diff --git a/src/future/aws/PhutilAWSv4Signature.php b/src/future/aws/PhutilAWSv4Signature.php
--- a/src/future/aws/PhutilAWSv4Signature.php
+++ b/src/future/aws/PhutilAWSv4Signature.php
@@ -242,14 +242,10 @@
 
   private function getCanonicalParameterList(HTTPSFuture $future) {
     $uri = new PhutilURI($future->getURI());
-    $params = $uri->getQueryParams();
+    $params = $uri->getQueryParamsAsMap();
 
     ksort($params);
-    $canonical_parameters = array();
-    foreach ($params as $key => $value) {
-      $canonical_parameters[] = rawurlencode($key).'='.rawurlencode($value);
-    }
-    $canonical_parameters = implode('&', $canonical_parameters);
+    $canonical_parameters = phutil_build_http_querystring($params);
 
     return $canonical_parameters;
   }
diff --git a/src/future/oauth/PhutilOAuth1Future.php b/src/future/oauth/PhutilOAuth1Future.php
--- a/src/future/oauth/PhutilOAuth1Future.php
+++ b/src/future/oauth/PhutilOAuth1Future.php
@@ -94,7 +94,7 @@
     }
 
     $params = $params
-            + $this->uri->getQueryParams()
+            + $this->uri->getQueryParamsAsMap()
             + $this->getOAuth1Headers();
 
     return $this->sign($params);
diff --git a/src/parser/PhutilURI.php b/src/parser/PhutilURI.php
--- a/src/parser/PhutilURI.php
+++ b/src/parser/PhutilURI.php
@@ -123,8 +123,13 @@
     $this->path = idx($parts, 'path', '');
     $query = idx($parts, 'query');
     if ($query) {
-      $this->query = id(new PhutilQueryStringParser())->parseQueryString(
-        $query);
+      $pairs = id(new PhutilQueryStringParser())
+        ->parseQueryStringToPairList($query);
+
+      foreach ($pairs as $pair) {
+        list($key, $value) = $pair;
+        $this->appendQueryParam($key, $value);
+      }
     }
     $this->fragment = idx($parts, 'fragment', '');
 
@@ -174,7 +179,7 @@
     }
 
     if ($this->query) {
-      $query = '?'.phutil_build_http_querystring($this->query);
+      $query = '?'.phutil_build_http_querystring_from_pairs($this->query);
     } else {
       $query = null;
     }
@@ -196,23 +201,114 @@
   }
 
   public function setQueryParam($key, $value) {
-    if ($value === null) {
-      unset($this->query[$key]);
-    } else {
-      $this->query[$key] = $value;
+    // To set, we replace the first matching key with the new value, then
+    // remove all other matching keys. This replaces the old value and retains
+    // the parameter order.
+
+    $is_null = ($value === null);
+
+    // Typecheck and cast the key before we compare it to existing keys. This
+    // raises an early exception if the key has a bad type.
+    list($key) = phutil_http_parameter_pair($key, '');
+
+    $found = false;
+    foreach ($this->query as $list_key => $pair) {
+      list($k, $v) = $pair;
+
+      if ($k !== $key) {
+        continue;
+      }
+
+      if ($found) {
+        unset($this->query[$list_key]);
+        continue;
+      }
+
+      $found = true;
+
+      if ($is_null) {
+        unset($this->query[$list_key]);
+      } else {
+        $this->insertQueryParam($key, $value, $list_key);
+      }
+    }
+
+    $this->query = array_values($this->query);
+
+    // If we didn't find an existing place to put it, add it to the end.
+    if (!$found) {
+      if (!$is_null) {
+        $this->appendQueryParam($key, $value);
+      }
     }
+
     return $this;
   }
 
   public function setQueryParams(array $params) {
-    $this->query = $params;
+    $this->query = array();
+
+    foreach ($params as $k => $v) {
+      $this->appendQueryParam($k, $v);
+    }
+
     return $this;
   }
 
+  /**
+   * @deprecated
+   */
   public function getQueryParams() {
+    $map = array();
+
+    foreach ($this->query as $pair) {
+      list($k, $v) = $pair;
+      $map[$k] = $v;
+    }
+
+    return $map;
+  }
+
+  public function getQueryParamsAsMap() {
+    $map = array();
+
+    foreach ($this->query as $pair) {
+      list($k, $v) = $pair;
+
+      if (isset($map[$k])) {
+        throw new Exception(
+          pht(
+            'Query parameters include a duplicate key ("%s") and can not be '.
+            'nondestructively represented as a map.',
+            $k));
+      }
+
+      $map[$k] = $v;
+    }
+
+    return $map;
+  }
+
+  public function getQueryParamsAsPairList() {
     return $this->query;
   }
 
+  public function appendQueryParam($key, $value) {
+    return $this->insertQueryParam($key, $value);
+  }
+
+  private function insertQueryParam($key, $value, $idx = null) {
+    list($key, $value) = phutil_http_parameter_pair($key, $value);
+
+    if ($idx === null) {
+      $this->query[] = array($key, $value);
+    } else {
+      $this->query[$idx] = array($key, $value);
+    }
+
+    return $this;
+  }
+
   public function setProtocol($protocol) {
     $this->protocol = $protocol;
     return $this;
diff --git a/src/parser/__tests__/PhutilURITestCase.php b/src/parser/__tests__/PhutilURITestCase.php
--- a/src/parser/__tests__/PhutilURITestCase.php
+++ b/src/parser/__tests__/PhutilURITestCase.php
@@ -16,9 +16,12 @@
     $this->assertEqual('/path/', $uri->getPath(), pht('path'));
     $this->assertEqual(
       array(
-        'query' => 'value',
+        array(
+          'query',
+          'value',
+        ),
       ),
-      $uri->getQueryParams(),
+      $uri->getQueryParamsAsPairList(),
       'query params');
     $this->assertEqual('fragment', $uri->getFragment(), pht('fragment'));
     $this->assertEqual(
@@ -37,7 +40,7 @@
     $this->assertEqual('/example/example.git', $uri->getPath(), pht('path'));
     $this->assertEqual(
       array(),
-      $uri->getQueryParams(),
+      $uri->getQueryParamsAsPairList(),
       pht('query parameters'));
     $this->assertEqual('', $uri->getFragment(), pht('fragment'));
     $this->assertEqual(
@@ -183,9 +186,12 @@
     $this->assertEqual('', $uri->getPath(), pht('path'));
     $this->assertEqual(
       array(
-        'x' => '/',
+        array(
+          'x',
+          '/',
+        ),
       ),
-      $uri->getQueryParams());
+      $uri->getQueryParamsAsPairList());
 
     // This is not a legitimate URI and should not parse as one.
     $uri = new PhutilURI('fruit.list: apple banana cherry');
@@ -275,4 +281,111 @@
     $this->assertTrue($caught instanceof Exception);
   }
 
+  public function testDuplicateKeys() {
+    $uri = new PhutilURI('http://www.example.com/?x=1&x=2');
+    $this->assertEqual(
+      'http://www.example.com/?x=1&x=2',
+      (string)$uri);
+
+    $uri->appendQueryParam('x', '3');
+    $this->assertEqual(
+      'http://www.example.com/?x=1&x=2&x=3',
+      (string)$uri);
+
+    $uri->setQueryParam('x', '4');
+    $this->assertEqual(
+      'http://www.example.com/?x=4',
+      (string)$uri);
+
+    $uri->setQueryParam('x', null);
+    $this->assertEqual(
+      'http://www.example.com/',
+      (string)$uri);
+
+    $uri->appendQueryParam('a', 'a');
+    $uri->appendQueryParam('b', 'b');
+    $uri->appendQueryParam('c', 'c');
+    $uri->appendQueryParam('b', 'd');
+
+    $this->assertEqual(
+      'http://www.example.com/?a=a&b=b&c=c&b=d',
+      (string)$uri);
+
+    $uri->setQueryParam('b', 'e');
+    $this->assertEqual(
+      'http://www.example.com/?a=a&b=e&c=c',
+      (string)$uri,
+      pht(
+        'Replacing a parameter should retain position and overwrite other '.
+        'instances of the key.'));
+  }
+
+  public function testBadHTTPParameters() {
+    $uri = new PhutilURI('http://www.example.com/');
+
+    $caught = null;
+    try {
+      $uri->setQueryParam(array(), 'x');
+    } catch (Exception $ex) {
+      $caught = $ex;
+    }
+
+    $this->assertTrue(
+      (bool)$caught,
+      pht('Nonscalar HTTP keys should throw.'));
+
+    $caught = null;
+    try {
+      $uri->setQueryParam('x', array());
+    } catch (Exception $ex) {
+      $caught = $ex;
+    }
+
+    $this->assertTrue(
+      (bool)$caught,
+      pht('Nonscalar HTTP values should throw.'));
+  }
+
+  public function testHTTPParameterTypes() {
+    // Whether you pass an integer or string, "0" should always be the same
+    // query parameter.
+
+    $uri = new PhutilURI('http://www.example.com/');
+
+    $uri->appendQueryParam(0, 'a');
+    $uri->appendQueryParam('0', 'b');
+    $this->assertEqual(
+      'http://www.example.com/?0=a&0=b',
+      (string)$uri);
+
+    $uri->setQueryParam(0, 'c');
+    $this->assertEqual(
+      'http://www.example.com/?0=c',
+      (string)$uri);
+
+    $uri->setQueryParam(0, 'a');
+    $uri->appendQueryParam('0', 'b');
+    $this->assertEqual(
+      'http://www.example.com/?0=a&0=b',
+      (string)$uri);
+
+    $uri->setQueryParam('0', 'c');
+    $this->assertEqual(
+      'http://www.example.com/?0=c',
+      (string)$uri);
+  }
+
+  public function testGetQueryParamsAsMap() {
+    $uri = new PhutilURI('http://www.example.com/?x=1&x=2');
+
+    $caught = null;
+    try {
+      $map = $uri->getQueryParamsAsMap();
+    } catch (Exception $ex) {
+      $caught = $ex;
+    }
+
+    $this->assertTrue((bool)$caught);
+  }
+
 }
diff --git a/src/utils/utils.php b/src/utils/utils.php
--- a/src/utils/utils.php
+++ b/src/utils/utils.php
@@ -1567,19 +1567,37 @@
  * @return string HTTP query string.
  */
 function phutil_build_http_querystring(array $parameters) {
+  $pairs = array();
+  foreach ($parameters as $key => $value) {
+    $pairs[] = array($key, $value);
+  }
+
+  return phutil_build_http_querystring_from_pairs($pairs);
+}
+
+/**
+ * Build a query string from a list of parameter pairs.
+ *
+ * @param list<pair<string, string>> List of pairs.
+ * @return string HTTP query string.
+ */
+function phutil_build_http_querystring_from_pairs(array $pairs) {
   // We want to encode in RFC3986 mode, but "http_build_query()" did not get
   // a flag for that mode until PHP 5.4.0. This is equivalent to calling
   // "http_build_query()" with the "PHP_QUERY_RFC3986" flag.
 
   $query = array();
-  foreach ($parameters as $key => $value) {
-    if (is_array($value) || is_object($value)) {
+  foreach ($pairs as $pair_key => $pair) {
+    if (!is_array($pair) || (count($pair) !== 2)) {
       throw new Exception(
         pht(
-          'HTTP query parameter (with key "%s") is not a scalar. Parameters '.
-          'must all be scalars.',
-          $key));
+          'HTTP parameter pair (with key "%s") is not valid: each pair must '.
+          'be an array with exactly two elements.',
+          $pair_key));
     }
+
+    list($key, $value) = $pair;
+    list($key, $value) = phutil_http_parameter_pair($key, $value);
     $query[] = rawurlencode($key).'='.rawurlencode($value);
   }
   $query = implode($query, '&');
@@ -1587,6 +1605,41 @@
   return $query;
 }
 
+/**
+ * Typecheck and cast an HTTP key-value parameter pair.
+ *
+ * Scalar values are converted to strings. Nonscalar values raise exceptions.
+ *
+ * @param scalar HTTP parameter key.
+ * @param scalar HTTP parameter value.
+ * @return pair<string, string> Key and value as strings.
+ */
+function phutil_http_parameter_pair($key, $value) {
+  try {
+    assert_stringlike($key);
+  } catch (InvalidArgumentException $ex) {
+    throw new PhutilProxyException(
+      pht('HTTP query parameter key must be a scalar.'),
+      $ex);
+  }
+
+  $key = (string)$key;
+
+  try {
+    assert_stringlike($value);
+  } catch (InvalidArgumentException $ex) {
+    throw new PhutilProxyException(
+      pht(
+        'HTTP query parameter value (for key "%s") must be a scalar.',
+        $key),
+      $ex);
+  }
+
+  $value = (string)$value;
+
+  return array($key, $value);
+}
+
 function phutil_decode_mime_header($header) {
   if (function_exists('iconv_mime_decode')) {
     return iconv_mime_decode($header, 0, 'UTF-8');