diff --git a/hgext/journal.py b/hgext/journal.py
--- a/hgext/journal.py
+++ b/hgext/journal.py
@@ -127,7 +127,10 @@ def recordbookmarks(orig, store, fp):
     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)
diff --git a/tests/test-journal.t b/tests/test-journal.t
--- a/tests/test-journal.t
+++ b/tests/test-journal.t
@@ -91,6 +91,7 @@ Test that we tracks bookmark deletion
   $ 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 @@ Test that you can list all entries as we
   $ 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 @@ Test that you can list all entries as we
   $ 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 @@ Test that verbose, JSON, template and co
   $ 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