diff --git a/mercurial/url.py b/mercurial/url.py
--- a/mercurial/url.py
+++ b/mercurial/url.py
@@ -225,7 +225,7 @@
 
 def _generic_proxytunnel(self):
     proxyheaders = {
-        x: self.headers[x]
+        pycompat.bytestr(x): pycompat.bytestr(self.headers[x])
         for x in self.headers
         if x.lower().startswith('proxy-')
     }