--- a/hgext/journal.py	Fri Jul 21 15:28:52 2023 +0200
+++ b/hgext/journal.py	Fri Jul 21 15:26:15 2023 +0200
@@ -127,7 +127,10 @@
     repo = store._repo
     if util.safehasattr(repo, 'journal'):
         oldmarks = bookmarks.bmstore(repo)
-        for mark, value in store.items():
+        all_marks = set(b for b, n in oldmarks.items())
+        all_marks.update(b for b, n in store.items())
+        for mark in sorted(all_marks):
+            value = store.get(mark, repo.nullid)
             oldvalue = oldmarks.get(mark, repo.nullid)
             if value != oldvalue:
                 repo.journal.record(bookmarktype, mark, oldvalue, value)

--- a/tests/test-journal.t	Fri Jul 21 15:28:52 2023 +0200
+++ b/tests/test-journal.t	Fri Jul 21 15:26:15 2023 +0200
@@ -91,6 +91,7 @@
   $ hg book -d babar
   $ hg journal babar
   previous locations of 'babar':
+  000000000000  book -d babar
   cb9a9f314b8b  book -f -r '.~1' babar
   1e6c11564562  book -r . babar
 
@@ -109,6 +110,7 @@
   $ hg journal --all
   previous locations of the working copy and bookmarks:
   1e6c11564562  baz       book -r tip baz
+  000000000000  babar     book -d babar
   cb9a9f314b8b  babar     book -f -r '.~1' babar
   1e6c11564562  babar     book -r . babar
   1e6c11564562  bar       up
@@ -139,6 +141,7 @@
   $ hg journal "re:ba."
   previous locations of 're:ba.':
   1e6c11564562  baz       book -r tip baz
+  000000000000  babar     book -d babar
   cb9a9f314b8b  babar     book -f -r '.~1' babar
   1e6c11564562  babar     book -r . babar
   1e6c11564562  bar       up
@@ -150,6 +153,7 @@
   $ hg journal --verbose --all
   previous locations of the working copy and bookmarks:
   000000000000 -> 1e6c11564562 foobar    baz      1970-01-01 00:00 +0000  book -r tip baz
+  cb9a9f314b8b -> 000000000000 foobar    babar    1970-01-01 00:00 +0000  book -d babar
   1e6c11564562 -> cb9a9f314b8b foobar    babar    1970-01-01 00:00 +0000  book -f -r '.~1' babar
   000000000000 -> 1e6c11564562 foobar    babar    1970-01-01 00:00 +0000  book -r . babar
   cb9a9f314b8b -> 1e6c11564562 foobar    bar      1970-01-01 00:00 +0000  up