diff --git a/rbtools/api/request.py b/rbtools/api/request.py
index c93e5aa68a98811abb2febb24b1b67c01fe67653..98ad8cdbfc1d91c476d0a6a5a0246e74e6a01c70 100644
--- a/rbtools/api/request.py
+++ b/rbtools/api/request.py
@@ -49,9 +49,8 @@ RB_COOKIE_NAME = 'rbsessionid'
 
 class HttpRequest(object):
     """High-level HTTP-request object."""
-    def __init__(self, url, method='GET', query_args={}):
+    def __init__(self, url, method='GET', query_args={}, headers={}):
         self.method = method
-        self.headers = {}
         self._fields = {}
         self._files = {}
 
@@ -62,13 +61,27 @@ class HttpRequest(object):
             for key, value in six.iteritems(query_args)
         ])
 
+        # Make sure headers are always in the native string type.
+        self.headers = {
+            str(key): str(value)
+            for key, value in six.iteritems(headers)
+        }
+
         # Add the query arguments to the url
-        url_parts = list(urlparse(url))
+        url_parts = list(urlparse(str(url)))
         query = dict(parse_qsl(url_parts[4]))
         query.update(query_args)
         url_parts[4] = urlencode(query)
         self.url = urlunparse(url_parts)
 
+    @property
+    def method(self):
+        return self._method
+
+    @method.setter
+    def method(self, method):
+        self._method = str(method)
+
     def add_field(self, name, value):
         self._fields[name] = value
 
@@ -157,9 +170,14 @@ class HttpRequest(object):
 
 class Request(URLRequest):
     """A request which contains a method attribute."""
-    def __init__(self, url, body='', headers={}, method='PUT'):
-        URLRequest.__init__(self, url, body, headers)
-        self.method = method
+    def __init__(self, url, body=b'', headers={}, method='PUT'):
+        normalized_headers = {
+            str(key): str(value)
+            for key, value in six.iteritems(headers)
+        }
+
+        URLRequest.__init__(self, str(url), body, normalized_headers)
+        self.method = str(method)
 
     def get_method(self):
         return self.method
@@ -513,7 +531,7 @@ class ReviewBoardServer(object):
 
         opener = build_opener(*handlers)
         opener.addheaders = [
-            ('User-agent', self.agent),
+            (str('User-agent'), str(self.agent)),
         ]
         install_opener(opener)
 
diff --git a/rbtools/api/resource.py b/rbtools/api/resource.py
index 1e129636ad3f01514ba615858853a89ea035c8b8..755a762bc72a27629b39ade3c04dbc906a464ae1 100644
--- a/rbtools/api/resource.py
+++ b/rbtools/api/resource.py
@@ -624,9 +624,9 @@ class DiffResource(ItemResource):
     @request_method_decorator
     def get_patch(self, **kwargs):
         """Retrieves the actual diff file contents."""
-        request = HttpRequest(self._url, query_args=kwargs)
-        request.headers['Accept'] = 'text/x-patch'
-        return request
+        return HttpRequest(self._url, query_args=kwargs, headers={
+            'Accept': 'text/x-patch',
+        })
 
 
 @resource_mimetype('application/vnd.reviewboard.org.file')
@@ -635,17 +635,16 @@ class FileDiffResource(ItemResource):
     @request_method_decorator
     def get_patch(self, **kwargs):
         """Retrieves the actual diff file contents."""
-        request = HttpRequest(self._url, query_args=kwargs)
-        request.headers['Accept'] = 'text/x-patch'
-        return request
+        return HttpRequest(self._url, query_args=kwargs, headers={
+            'Accept': 'text/x-patch',
+        })
 
     @request_method_decorator
     def get_diff_data(self, **kwargs):
         """Retrieves the actual raw diff data for the file."""
-        request = HttpRequest(self._url, query_args=kwargs)
-        request.headers['Accept'] = \
-            'application/vnd.reviewboard.org.diff.data+json'
-        return request
+        return HttpRequest(self._url, query_args=kwargs, headers={
+            'Accept': 'application/vnd.reviewboard.org.diff.data+json',
+        })
 
 
 @resource_mimetype('application/vnd.reviewboard.org.file-attachments')