diff --git a/mercurial/revlogutils/nodemap.py b/mercurial/revlogutils/nodemap.py
--- a/mercurial/revlogutils/nodemap.py
+++ b/mercurial/revlogutils/nodemap.py
@@ -9,6 +9,7 @@
 from __future__ import absolute_import
 
 import os
+import re
 import struct
 
 from .. import (
@@ -70,6 +71,16 @@
     data = persistent_data(revlog.index)
     uid = _make_uid()
     datafile = _rawdata_filepath(revlog, uid)
+    olds = _otherrawdata_filepath(revlog, uid)
+    if olds:
+        realvfs = getattr(revlog, '_realopener', revlog.opener)
+
+        def cleanup(tr):
+            for oldfile in olds:
+                realvfs.tryunlink(oldfile)
+
+        callback_id = b"revlog-cleanup-nodemap-%s" % revlog.nodemap_file
+        tr.addpostclose(callback_id, cleanup)
     # EXP-TODO: if this is a cache, this should use a cache vfs, not a
     # store vfs
     with revlog.opener(datafile, 'w') as fd:
@@ -135,6 +146,18 @@
     return b"%s-%s.nd" % (prefix, uid)
 
 
+def _otherrawdata_filepath(revlog, uid):
+    prefix = revlog.nodemap_file[:-2]
+    pattern = re.compile(b"(^|/)%s-[0-9a-f]+.nd$" % prefix)
+    newfilepath = _rawdata_filepath(revlog, uid)
+    dirpath = revlog.opener.dirname(newfilepath)
+    others = []
+    for f in revlog.opener.listdir(dirpath):
+        if pattern.match(f):
+            others.append(f)
+    return others
+
+
 ### Nodemap Trie
 #
 # This is a simple reference implementation to compute and serialise a nodemap
diff --git a/tests/test-persistent-nodemap.t b/tests/test-persistent-nodemap.t
--- a/tests/test-persistent-nodemap.t
+++ b/tests/test-persistent-nodemap.t
@@ -12,6 +12,8 @@
   $ hg debugbuilddag .+5000
   $ f --size .hg/store/00changelog.n
   .hg/store/00changelog.n: size=18
+  $ f --sha256 .hg/store/00changelog-*.nd
+  .hg/store/00changelog-????????????????.nd: sha256=bc400bf49f11e83bbd25630439feee6628a80a8602d2e38972eac44cc3efe10c (glob)
   $ hg debugnodemap --dump-new | f --sha256 --size
   size=245760, sha256=bc400bf49f11e83bbd25630439feee6628a80a8602d2e38972eac44cc3efe10c
   $ hg debugnodemap --dump-disk | f --sha256 --bytes=256 --hexdump --size
@@ -32,3 +34,15 @@
   00d0: ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff |................|
   00e0: ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff |................|
   00f0: ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff |................|
+
+add a new commit
+
+  $ hg up
+  0 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  $ echo foo > foo
+  $ hg add foo
+  $ hg ci -m 'foo'
+  $ f --size .hg/store/00changelog.n
+  .hg/store/00changelog.n: size=18
+  $ f --sha256 .hg/store/00changelog-*.nd --size
+  .hg/store/00changelog-????????????????.nd: size=245760, sha256=e6ee5d59afaab2cb1afae1077715be280578d29df508bd3dd9d74a994bc555e7 (glob)