diff --git a/src/parser/PhutilURI.php b/src/parser/PhutilURI.php
--- a/src/parser/PhutilURI.php
+++ b/src/parser/PhutilURI.php
@@ -27,7 +27,7 @@
   const TYPE_URI = 'uri';
   const TYPE_GIT = 'git';
 
-  public function __construct($uri) {
+  public function __construct($uri, $params = array()) {
     if ($uri instanceof PhutilURI) {
       $this->protocol = $uri->protocol;
       $this->user = $uri->user;
@@ -38,10 +38,13 @@
       $this->query = $uri->query;
       $this->fragment = $uri->fragment;
       $this->type = $uri->type;
+
+      $this->initializeQueryParams(phutil_string_cast($uri), $params);
+
       return;
     }
 
-    $uri = (string)$uri;
+    $uri = phutil_string_cast($uri);
 
     $type = self::TYPE_URI;
 
@@ -134,6 +137,8 @@
     $this->fragment = idx($parts, 'fragment', '');
 
     $this->type = $type;
+
+    $this->initializeQueryParams($uri, $params);
   }
 
   public function __toString() {
@@ -200,6 +205,9 @@
     return $prefix.$path.$query.$fragment;
   }
 
+  /**
+   * @deprecated
+   */
   public function setQueryParam($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
@@ -245,6 +253,9 @@
     return $this;
   }
 
+  /**
+   * @deprecated
+   */
   public function setQueryParams(array $params) {
     $this->query = array();
 
@@ -297,6 +308,43 @@
     return $this->insertQueryParam($key, $value);
   }
 
+  public function removeAllQueryParams() {
+    $this->query = array();
+    return $this;
+  }
+
+  public function removeQueryParam($remove_key) {
+    list($remove_key) = phutil_http_parameter_pair($remove_key, '');
+
+    foreach ($this->query as $idx => $pair) {
+      list($key, $value) = $pair;
+
+      if ($key !== $remove_key) {
+        continue;
+      }
+
+      unset($this->query[$idx]);
+    }
+
+    $this->query = array_values($this->query);
+
+    return $this;
+  }
+
+  public function replaceQueryParam($replace_key, $replace_value) {
+    if ($replace_value === null) {
+      throw new InvalidArgumentException(
+        pht(
+          'Value provided to "replaceQueryParam()" for key "%s" is NULL. '.
+          'Use "removeQueryParam()" to remove a query parameter.',
+          $replace_key));
+    }
+
+    $this->removeQueryParam($replace_key);
+    $this->appendQueryParam($replace_key, $replace_value);
+    return $this;
+  }
+
   private function insertQueryParam($key, $value, $idx = null) {
     list($key, $value) = phutil_http_parameter_pair($key, $value);
 
@@ -309,6 +357,34 @@
     return $this;
   }
 
+  private function initializeQueryParams($uri, array $params) {
+    $have_params = array();
+    foreach ($this->query as $pair) {
+      list($key) = $pair;
+      $have_params[$key] = true;
+    }
+
+    foreach ($params as $key => $value) {
+      if (isset($have_params[$key])) {
+        throw new InvalidArgumentException(
+          pht(
+            'You are trying to construct an ambiguous URI: query parameter '.
+            '"%s" is present in both the string argument ("%s") and the map '.
+            'argument.',
+            $key,
+            $uri));
+      }
+
+      if ($value === null) {
+        continue;
+      }
+
+      $this->appendQueryParam($key, $value);
+    }
+
+    return $this;
+  }
+
   public function setProtocol($protocol) {
     $this->protocol = $protocol;
     return $this;
@@ -410,7 +486,7 @@
 
   public function alter($key, $value) {
     $altered = clone $this;
-    $altered->setQueryParam($key, $value);
+    $altered->replaceQueryParam($key, $value);
     return $altered;
   }
 
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
@@ -292,12 +292,12 @@
       'http://www.example.com/?x=1&x=2&x=3',
       (string)$uri);
 
-    $uri->setQueryParam('x', '4');
+    $uri->replaceQueryParam('x', '4');
     $this->assertEqual(
       'http://www.example.com/?x=4',
       (string)$uri);
 
-    $uri->setQueryParam('x', null);
+    $uri->removeQueryParam('x');
     $this->assertEqual(
       'http://www.example.com/',
       (string)$uri);
@@ -311,13 +311,12 @@
       'http://www.example.com/?a=a&b=b&c=c&b=d',
       (string)$uri);
 
-    $uri->setQueryParam('b', 'e');
+    $uri->replaceQueryParam('b', 'e');
     $this->assertEqual(
-      'http://www.example.com/?a=a&b=e&c=c',
+      'http://www.example.com/?a=a&c=c&b=e',
       (string)$uri,
       pht(
-        'Replacing a parameter should retain position and overwrite other '.
-        'instances of the key.'));
+        'Replacing a parameter should overwrite other instances of the key.'));
   }
 
   public function testBadHTTPParameters() {
@@ -325,7 +324,7 @@
 
     $caught = null;
     try {
-      $uri->setQueryParam(array(), 'x');
+      $uri->replaceQueryParam(array(), 'x');
     } catch (Exception $ex) {
       $caught = $ex;
     }
@@ -336,7 +335,7 @@
 
     $caught = null;
     try {
-      $uri->setQueryParam('x', array());
+      $uri->replaceQueryParam('x', array());
     } catch (Exception $ex) {
       $caught = $ex;
     }
@@ -358,18 +357,18 @@
       'http://www.example.com/?0=a&0=b',
       (string)$uri);
 
-    $uri->setQueryParam(0, 'c');
+    $uri->replaceQueryParam(0, 'c');
     $this->assertEqual(
       'http://www.example.com/?0=c',
       (string)$uri);
 
-    $uri->setQueryParam(0, 'a');
+    $uri->replaceQueryParam(0, 'a');
     $uri->appendQueryParam('0', 'b');
     $this->assertEqual(
       'http://www.example.com/?0=a&0=b',
       (string)$uri);
 
-    $uri->setQueryParam('0', 'c');
+    $uri->replaceQueryParam('0', 'c');
     $this->assertEqual(
       'http://www.example.com/?0=c',
       (string)$uri);
@@ -388,4 +387,31 @@
     $this->assertTrue((bool)$caught);
   }
 
+  public function testQueryURIConstruction() {
+    $uri = new PhutilURI('http://example.com/', array('y' => '1'));
+    $this->assertEqual(
+      'http://example.com/?y=1',
+      (string)$uri);
+
+    $uri = new PhutilURI('http://example.com/?x=2', array('y' => '1'));
+    $this->assertEqual(
+      'http://example.com/?x=2&y=1',
+      (string)$uri);
+
+    $caught = null;
+    try {
+      $uri = new PhutilURI('http://example.com/?y=3', array('y' => '1'));
+    } catch (InvalidArgumentException $ex) {
+      $caught = $ex;
+    }
+    $this->assertTrue((bool)$caught);
+
+    $uri = new PhutilURI('http://example.com/?a=1', array('b' => '2'));
+    $uri = new PhutilURI($uri, array('c' => '3'));
+
+    $this->assertEqual(
+      'http://example.com/?a=1&b=2&c=3',
+      (string)$uri);
+  }
+
 }
diff --git a/src/utils/utils.php b/src/utils/utils.php
--- a/src/utils/utils.php
+++ b/src/utils/utils.php
@@ -1623,7 +1623,7 @@
       $ex);
   }
 
-  $key = (string)$key;
+  $key = phutil_string_cast($key);
 
   try {
     assert_stringlike($value);
@@ -1635,7 +1635,7 @@
       $ex);
   }
 
-  $value = (string)$value;
+  $value = phutil_string_cast($value);
 
   return array($key, $value);
 }