diff --git a/googleapiclient/discovery.py b/googleapiclient/discovery.py
index 45ae80a..afba86f 100644
--- a/googleapiclient/discovery.py
+++ b/googleapiclient/discovery.py
@@ -491,6 +491,23 @@
   return path_url, http_method, method_id, accept, max_size, media_path_url
 
 
+def _urljoin(base, url):
+  """Custom urljoin replacement supporting : before / in url."""
+  # In general, it's unsafe to simply join base and url. However, for
+  # the case of discovery documents, we know:
+  #  * base will never contain params, query, or fragment
+  #  * url will never contain a scheme or net_loc.
+  # In general, this means we can safely join on /; we just need to
+  # ensure we end up with precisely one / joining base and url. The
+  # exception here is the case of media uploads, where url will be an
+  # absolute url.
+  if url.startswith('http://') or url.startswith('https://'):
+    return urlparse.urljoin(base, url)
+  new_base = base if base.endswith('/') else base + '/'
+  new_url = url[1:] if url.startswith('/') else url
+  return new_base + new_url
+
+
 # TODO(dhermes): Convert this class to ResourceMethod and make it callable
 class ResourceMethodParameters(object):
   """Represents the parameters associated with a method.
@@ -671,7 +688,7 @@
         actual_path_params, actual_query_params, body_value)
 
     expanded_url = uritemplate.expand(pathUrl, params)
-    url = urlparse.urljoin(self._baseUrl, expanded_url + query)
+    url = _urljoin(self._baseUrl, expanded_url + query)
 
     resumable = None
     multipart_boundary = ''
@@ -697,7 +714,7 @@
 
       # Use the media path uri for media uploads
       expanded_url = uritemplate.expand(mediaPathUrl, params)
-      url = urlparse.urljoin(self._baseUrl, expanded_url + query)
+      url = _urljoin(self._baseUrl, expanded_url + query)
       if media_upload.resumable():
         url = _add_query_parameter(url, 'uploadType', 'resumable')
 
diff --git a/tests/test_discovery.py b/tests/test_discovery.py
index a2593e2..a5f2541 100644
--- a/tests/test_discovery.py
+++ b/tests/test_discovery.py
@@ -26,6 +26,7 @@
 import copy
 import datetime
 import httplib2
+import itertools
 import json
 import os
 import pickle
@@ -44,6 +45,7 @@
 from googleapiclient.discovery import _fix_up_media_upload
 from googleapiclient.discovery import _fix_up_method_description
 from googleapiclient.discovery import _fix_up_parameters
+from googleapiclient.discovery import _urljoin
 from googleapiclient.discovery import build
 from googleapiclient.discovery import build_from_document
 from googleapiclient.discovery import DISCOVERY_URI
@@ -268,6 +270,24 @@
     self.assertEqual(result, (path_url, http_method, method_id, accept,
                               max_size, media_path_url))
 
+  def test_urljoin(self):
+    # We want to exhaustively test various URL combinations.
+    simple_bases = ['https://www.googleapis.com', 'https://www.googleapis.com/']
+    long_urls = ['foo/v1/bar:custom?alt=json', '/foo/v1/bar:custom?alt=json']
+
+    long_bases = [
+      'https://www.googleapis.com/foo/v1',
+      'https://www.googleapis.com/foo/v1/',
+    ]
+    simple_urls = ['bar:custom?alt=json', '/bar:custom?alt=json']
+
+    final_url = 'https://www.googleapis.com/foo/v1/bar:custom?alt=json'
+    for base, url in itertools.product(simple_bases, long_urls):
+      self.assertEqual(final_url, _urljoin(base, url))
+    for base, url in itertools.product(long_bases, simple_urls):
+      self.assertEqual(final_url, _urljoin(base, url))
+
+
   def test_ResourceMethodParameters_zoo_get(self):
     parameters = ResourceMethodParameters(self.zoo_get_method_desc)