diff --git a/hgext/histedit.py b/hgext/histedit.py
--- a/hgext/histedit.py
+++ b/hgext/histedit.py
@@ -925,6 +925,13 @@ def _histedit(ui, repo, state, *freeargs
                     for n in succs[1:]:
                         ui.debug(m % node.short(n))
 
+    if supportsmarkers:
+        # Only create markers if the temp nodes weren't already removed.
+        obsolete.createmarkers(repo, ((repo[t],()) for t in sorted(tmpnodes)
+                                       if t in repo))
+    else:
+        cleanupnode(ui, repo, 'temp', tmpnodes)
+
     if not state.keep:
         if mapping:
             movebookmarks(ui, repo, mapping, state.topmost, ntm)
@@ -941,7 +948,6 @@ def _histedit(ui, repo, state, *freeargs
         else:
             cleanupnode(ui, repo, 'replaced', mapping)
 
-    cleanupnode(ui, repo, 'temp', tmpnodes)
     state.clear()
     if os.path.exists(repo.sjoin('undo')):
         os.unlink(repo.sjoin('undo'))
diff --git a/tests/test-histedit-arguments.t b/tests/test-histedit-arguments.t
--- a/tests/test-histedit-arguments.t
+++ b/tests/test-histedit-arguments.t
@@ -253,6 +253,7 @@ short hash. This tests issue3893.
   1 files updated, 0 files merged, 0 files removed, 0 files unresolved
   0 files updated, 0 files merged, 0 files removed, 0 files unresolved
   saved backup bundle to $TESTTMP/foo/.hg/strip-backup/*-backup.hg (glob)
+  saved backup bundle to $TESTTMP/foo/.hg/strip-backup/c8e68270e35a-23a13bf9-backup.hg (glob)
 
   $ hg update -q 2
   $ echo x > x
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
@@ -85,6 +85,7 @@
   > fold e860deea161a 4 e
   > pick 652413bf663e 5 f
   > EOF
+  saved backup bundle to $TESTTMP/r/.hg/strip-backup/96e494a2d553-3c6c5d92-backup.hg (glob)
   histedit: moving bookmarks also-two from 177f92b77385 to b346ab9a313d
   histedit: moving bookmarks five from 652413bf663e to cacdfd884a93
   histedit: moving bookmarks four from e860deea161a to 59d9f330561f
@@ -92,7 +93,6 @@
   histedit: moving bookmarks two from 177f92b77385 to b346ab9a313d
   histedit: moving bookmarks will-move-backwards from d2ae7f538514 to cb9a9f314b8b
   saved backup bundle to $TESTTMP/r/.hg/strip-backup/d2ae7f538514-48787b8d-backup.hg (glob)
-  saved backup bundle to $TESTTMP/r/.hg/strip-backup/96e494a2d553-3c6c5d92-backup.hg (glob)
   $ hg log --graph
   @  changeset:   3:cacdfd884a93
   |  bookmark:    five
diff --git a/tests/test-histedit-commute.t b/tests/test-histedit-commute.t
--- a/tests/test-histedit-commute.t
+++ b/tests/test-histedit-commute.t
@@ -424,6 +424,7 @@ Now, let's try to fold the second commit
   0 files updated, 0 files merged, 0 files removed, 0 files unresolved
   0 files updated, 0 files merged, 0 files removed, 0 files unresolved
   saved backup bundle to $TESTTMP/issue4251/.hg/strip-backup/*-backup.hg (glob)
+  saved backup bundle to $TESTTMP/issue4251/.hg/strip-backup/b0f4233702ca-d99e7186-backup.hg (glob)
 
   $ hg --config diff.git=yes export 0
   # HG changeset patch
diff --git a/tests/test-histedit-fold.t b/tests/test-histedit-fold.t
--- a/tests/test-histedit-fold.t
+++ b/tests/test-histedit-fold.t
@@ -390,7 +390,8 @@ dropped revision.
   HG: changed file
   1 files updated, 0 files merged, 0 files removed, 0 files unresolved
   0 files updated, 0 files merged, 0 files removed, 0 files unresolved
-  saved backup bundle to $TESTTMP/fold-with-dropped/.hg/strip-backup/617f94f13c0f-3d69522c-backup.hg (glob)
+  saved backup bundle to $TESTTMP/fold-with-dropped/.hg/strip-backup/55c8d8dc79ce-4066cd98-backup.hg (glob)
+  saved backup bundle to $TESTTMP/fold-with-dropped/.hg/strip-backup/617f94f13c0f-a35700fc-backup.hg (glob)
   $ hg logt -G
   @  1:10c647b2cdd5 +4
   |
diff --git a/tests/test-histedit-obsolete.t b/tests/test-histedit-obsolete.t
--- a/tests/test-histedit-obsolete.t
+++ b/tests/test-histedit-obsolete.t
@@ -64,12 +64,16 @@ Enable obsolete
   > fold e860deea161a 4 e
   > pick 652413bf663e 5 f
   > EOF
-  saved backup bundle to $TESTTMP/base/.hg/strip-backup/96e494a2d553-3c6c5d92-backup.hg (glob)
+  [1]
   $ hg log --graph --hidden
-  @  8:cacdfd884a93 f
+  @  10:cacdfd884a93 f
+  |
+  o  9:59d9f330561f d
   |
-  o  7:59d9f330561f d
-  |
+  | x  8:b558abc46d09 fold-temp-revision e860deea161a
+  | |
+  | x  7:96e494a2d553 d
+  |/
   o  6:b346ab9a313d c
   |
   | x  5:652413bf663e f
@@ -85,6 +89,8 @@ Enable obsolete
   o  0:cb9a9f314b8b a
   
   $ hg debugobsolete
+  96e494a2d553dd05902ba1cee1d94d4cb7b8faed 0 {b346ab9a313db8537ecf96fca3ca3ca984ef3bd7} (*) {'user': 'test'} (glob)
+  b558abc46d09c30f57ac31e85a8a3d64d2e906e4 0 {96e494a2d553dd05902ba1cee1d94d4cb7b8faed} (*) {'user': 'test'} (glob)
   d2ae7f538514cd87c17547b0de4cea71fe1af9fb 0 {cb9a9f314b8b07ba71012fcdbc544b5a4d82ff5b} (*) {'user': 'test'} (glob)
   177f92b773850b59254aa5e923436f921b55483b b346ab9a313db8537ecf96fca3ca3ca984ef3bd7 0 (*) {'user': 'test'} (glob)
   055a42cdd88768532f9cf79daa407fc8d138de9b 59d9f330561fd6c88b1a6b32f0e45034d88db784 0 (*) {'user': 'test'} (glob)
@@ -105,7 +111,7 @@ create an hidden revision
   0 files updated, 0 files merged, 3 files removed, 0 files unresolved
   0 files updated, 0 files merged, 0 files removed, 0 files unresolved
   $ hg log --graph
-  @  9:c13eb81022ca f
+  @  11:c13eb81022ca f
   |
   o  6:b346ab9a313d c
   |
@@ -127,7 +133,7 @@ Test that rewriting leaving instability 
   $ hg up '.^'
   0 files updated, 0 files merged, 1 files removed, 0 files unresolved
   $ hg log -r 'children(.)'
-  9:c13eb81022ca f (no-eol)
+  11:c13eb81022ca f (no-eol)
   $ hg histedit -r '.' --commands - <<EOF
   > edit b346ab9a313d 6 c
   > EOF
@@ -141,12 +147,12 @@ Test that rewriting leaving instability 
   0 files updated, 0 files merged, 0 files removed, 0 files unresolved
 
   $ hg log -r 'unstable()'
-  9:c13eb81022ca f (no-eol)
+  11:c13eb81022ca f (no-eol)
 
 stabilise
 
   $ hg rebase  -r 'unstable()' -d .
-  rebasing 9:c13eb81022ca "f"
+  rebasing 11:c13eb81022ca "f"
   $ hg up tip -q
 
 Test dropping of changeset on the top of the stack
@@ -166,7 +172,7 @@ dropped changeset to be hidden.
   > EOF
   0 files updated, 0 files merged, 1 files removed, 0 files unresolved
   $ hg log -G
-  @  10:40db8afa467b c
+  @  12:40db8afa467b c
   |
   o  0:cb9a9f314b8b a
   
@@ -188,9 +194,9 @@ With rewritten ancestors
   0 files updated, 0 files merged, 0 files removed, 0 files unresolved
   0 files updated, 0 files merged, 0 files removed, 0 files unresolved
   $ hg log -G
-  @  15:ee6544123ab8 c
+  @  17:ee6544123ab8 c
   |
-  o  14:269e713e9eae g
+  o  16:269e713e9eae g
   |
   o  0:cb9a9f314b8b a
   
@@ -212,9 +218,9 @@ Check that histedit respect immutability
   $ hg ph -pv '.^'
   phase changed for 2 changesets
   $ hg log -G
-  @  11:b449568bf7fc (draft) f
+  @  13:b449568bf7fc (draft) f
   |
-  o  10:40db8afa467b (public) c
+  o  12:40db8afa467b (public) c
   |
   o  0:cb9a9f314b8b (public) a
   
@@ -234,19 +240,19 @@ Prepare further testing
   > done
   $ hg phase --force --secret .~2
   $ hg log -G
-  @  16:ee118ab9fa44 (secret) k
+  @  18:ee118ab9fa44 (secret) k
   |
-  o  15:3a6c53ee7f3d (secret) j
+  o  17:3a6c53ee7f3d (secret) j
   |
-  o  14:b605fb7503f2 (secret) i
+  o  16:b605fb7503f2 (secret) i
   |
-  o  13:7395e1ff83bd (draft) h
+  o  15:7395e1ff83bd (draft) h
   |
-  o  12:6b70183d2492 (draft) g
+  o  14:6b70183d2492 (draft) g
   |
-  o  11:b449568bf7fc (draft) f
+  o  13:b449568bf7fc (draft) f
   |
-  o  10:40db8afa467b (public) c
+  o  12:40db8afa467b (public) c
   |
   o  0:cb9a9f314b8b (public) a
   
@@ -284,19 +290,19 @@ New-commit as draft (default)
   0 files updated, 0 files merged, 0 files removed, 0 files unresolved
   0 files updated, 0 files merged, 0 files removed, 0 files unresolved
   $ hg log -G
-  @  22:12e89af74238 (secret) k
+  @  24:12e89af74238 (secret) k
   |
-  o  21:636a8687b22e (secret) j
+  o  23:636a8687b22e (secret) j
   |
-  o  20:ccaf0a38653f (secret) i
+  o  22:ccaf0a38653f (secret) i
   |
-  o  19:11a89d1c2613 (draft) h
+  o  21:11a89d1c2613 (draft) h
   |
-  o  18:c1dec7ca82ea (draft) g
+  o  20:c1dec7ca82ea (draft) g
   |
-  o  17:087281e68428 (draft) f
+  o  19:087281e68428 (draft) f
   |
-  o  10:40db8afa467b (public) c
+  o  12:40db8afa467b (public) c
   |
   o  0:cb9a9f314b8b (public) a
   
@@ -333,19 +339,19 @@ New-commit as draft (default)
   0 files updated, 0 files merged, 0 files removed, 0 files unresolved
   0 files updated, 0 files merged, 0 files removed, 0 files unresolved
   $ hg log -G
-  @  22:12e89af74238 (secret) k
+  @  24:12e89af74238 (secret) k
   |
-  o  21:636a8687b22e (secret) j
+  o  23:636a8687b22e (secret) j
   |
-  o  20:ccaf0a38653f (secret) i
+  o  22:ccaf0a38653f (secret) i
   |
-  o  19:11a89d1c2613 (draft) h
+  o  21:11a89d1c2613 (draft) h
   |
-  o  18:c1dec7ca82ea (draft) g
+  o  20:c1dec7ca82ea (draft) g
   |
-  o  17:087281e68428 (draft) f
+  o  19:087281e68428 (draft) f
   |
-  o  10:40db8afa467b (public) c
+  o  12:40db8afa467b (public) c
   |
   o  0:cb9a9f314b8b (public) a
   
@@ -375,19 +381,19 @@ It seems more important to present the s
   0 files updated, 0 files merged, 0 files removed, 0 files unresolved
   0 files updated, 0 files merged, 0 files removed, 0 files unresolved
   $ hg log -G
-  @  21:558246857888 (secret) k
+  @  23:558246857888 (secret) k
   |
-  o  20:28bd44768535 (secret) h
+  o  22:28bd44768535 (secret) h
   |
-  o  19:d5395202aeb9 (secret) i
+  o  21:d5395202aeb9 (secret) i
   |
-  o  18:21edda8e341b (secret) g
+  o  20:21edda8e341b (secret) g
   |
-  o  17:5ab64f3a4832 (secret) j
+  o  19:5ab64f3a4832 (secret) j
   |
-  o  11:b449568bf7fc (draft) f
+  o  13:b449568bf7fc (draft) f
   |
-  o  10:40db8afa467b (public) c
+  o  12:40db8afa467b (public) c
   |
   o  0:cb9a9f314b8b (public) a
   
@@ -428,33 +434,30 @@ Note that there is a few reordering in t
   0 files updated, 0 files merged, 2 files removed, 0 files unresolved
   2 files updated, 0 files merged, 0 files removed, 0 files unresolved
   0 files updated, 0 files merged, 0 files removed, 0 files unresolved
-  saved backup bundle to $TESTTMP/folding/.hg/strip-backup/58019c66f35f-96092fce-backup.hg (glob)
-  saved backup bundle to $TESTTMP/folding/.hg/strip-backup/83d1858e070b-f3469cf8-backup.hg (glob)
-  saved backup bundle to $TESTTMP/folding/.hg/strip-backup/859969f5ed7e-d89a19d7-backup.hg (glob)
   $ hg log -G
-  @  19:f9daec13fb98 (secret) i
+  @  27:f9daec13fb98 (secret) i
   |
-  o  18:49807617f46a (secret) g
+  o  24:49807617f46a (secret) g
   |
-  o  17:050280826e04 (draft) h
+  o  21:050280826e04 (draft) h
   |
-  o  10:40db8afa467b (public) c
+  o  12:40db8afa467b (public) c
   |
   o  0:cb9a9f314b8b (public) a
   
-  $ hg co 18
+  $ hg co 49807617f46a
   0 files updated, 0 files merged, 2 files removed, 0 files unresolved
   $ echo wat >> wat
   $ hg add wat
   $ hg ci -m 'add wat'
   created new head
-  $ hg merge 19
+  $ hg merge f9daec13fb98
   2 files updated, 0 files merged, 0 files removed, 0 files unresolved
   (branch merge, don't forget to commit)
   $ hg ci -m 'merge'
   $ echo not wat > wat
   $ hg ci -m 'modify wat'
-  $ hg histedit 17
+  $ hg histedit 050280826e04
   abort: cannot edit history that contains merges
   [255]
   $ cd ..