diff --git a/mercurial/tags.py b/mercurial/tags.py
--- a/mercurial/tags.py
+++ b/mercurial/tags.py
@@ -337,7 +337,7 @@ def _writetagcache(ui, repo, heads, tagf
     # them local encoding on input, we would lose info writing them to
     # the cache.
     cachefile.write('\n')
-    for (name, (node, hist)) in cachetags.iteritems():
+    for (name, (node, hist)) in sorted(cachetags.iteritems()):
         for n in hist:
             cachefile.write("%s %s\n" % (hex(n), name))
         cachefile.write("%s %s\n" % (hex(node), name))