diff --git a/hgext/bookmarks.py b/hgext/bookmarks.py
--- a/hgext/bookmarks.py
+++ b/hgext/bookmarks.py
@@ -457,7 +457,7 @@ def diffbookmarks(ui, repo, remote):
     lmarks = repo.listkeys('bookmarks')
     rmarks = remote.listkeys('bookmarks')
 
-    diff = set(rmarks) - set(lmarks)
+    diff = sorted(set(rmarks) - set(lmarks))
     for k in diff:
         ui.write("   %-25s %s\n" % (k, rmarks[k][:12]))