diff --git a/hgext/histedit.py b/hgext/histedit.py
--- a/hgext/histedit.py
+++ b/hgext/histedit.py
@@ -476,7 +476,7 @@ def histedit(ui, repo, *parent, **opts):
             newtip = sorted(replacemap.values(), key=repo.changelog.rev)[-1]
             copybms(oldtip, newtip)
 
-            for old, new in replacemap.iteritems():
+            for old, new in sorted(replacemap.iteritems()):
                 copybms(old, new)
                 # TODO update mq state
 
diff --git a/tests/test-histedit-bookmark-motion.t b/tests/test-histedit-bookmark-motion.t
--- a/tests/test-histedit-bookmark-motion.t
+++ b/tests/test-histedit-bookmark-motion.t
@@ -87,14 +87,14 @@
   histedit: Should update metadata for the following changes:
   histedit:  055a42cdd887 to ae467701c500
   histedit:     moving bookmarks three
+  histedit:  177f92b77385 to d36c0562f908
+  histedit:     moving bookmarks also-two, two
   histedit:  652413bf663e to 0efacef7cb48
   histedit:     moving bookmarks five
   histedit:  d2ae7f538514 to cb9a9f314b8b
   histedit:     moving bookmarks will-move-backwards
   histedit:  e860deea161a to ae467701c500
   histedit:     moving bookmarks four
-  histedit:  177f92b77385 to d36c0562f908
-  histedit:     moving bookmarks also-two, two
   saved backup bundle to $TESTTMP/r/.hg/strip-backup/d2ae7f538514-backup.hg
   saved backup bundle to $TESTTMP/r/.hg/strip-backup/34a9919932c1-backup.hg
   $ hg log --graph
@@ -149,9 +149,9 @@
   histedit: Should update metadata for the following changes:
   histedit:  0efacef7cb48 to 1be9c35b4cb2
   histedit:     moving bookmarks five
+  histedit:  0efacef7cb48 to 7c044e3e33a9
   histedit:  ae467701c500 to 1be9c35b4cb2
   histedit:     moving bookmarks four, three
-  histedit:  0efacef7cb48 to 7c044e3e33a9
   saved backup bundle to $TESTTMP/r/.hg/strip-backup/ae467701c500-backup.hg
 
 We expect 'five' to stay at tip, since the tipmost bookmark is most