diff --git a/mercurial/keepalive.py b/mercurial/keepalive.py
--- a/mercurial/keepalive.py
+++ b/mercurial/keepalive.py
@@ -298,11 +298,12 @@ class KeepAliveHandler(object):
 
     def _start_transaction(self, h, req):
         # What follows mostly reimplements HTTPConnection.request()
-        # except it adds self.parent.addheaders in the mix.
-        headers = dict(self.parent.addheaders)
-        headers.update(req.headers)
-        headers.update(req.unredirected_hdrs)
-        headers = dict((n.lower(), v) for n, v in headers.items())
+        # except it adds self.parent.addheaders in the mix and sends headers
+        # in a deterministic order (to make testing easier).
+        headers = util.sortdict(self.parent.addheaders)
+        headers.update(sorted(req.headers.items()))
+        headers.update(sorted(req.unredirected_hdrs.items()))
+        headers = util.sortdict((n.lower(), v) for n, v in headers.items())
         skipheaders = {}
         for n in ('host', 'accept-encoding'):
             if n in headers: