diff --git a/mercurial/bookmarks.py b/mercurial/bookmarks.py
--- a/mercurial/bookmarks.py
+++ b/mercurial/bookmarks.py
@@ -256,7 +256,7 @@ def validdest(repo, old, new):
     elif repo.obsstore:
         # We only need this complicated logic if there is obsolescence
         # XXX will probably deserve an optimised revset.
-
+        nm = repo.changelog.nodemap
         validdests = set([old])
         plen = -1
         # compute the whole set of successors or descendants
@@ -268,7 +268,8 @@ def validdest(repo, old, new):
                     # obsolescence marker does not apply to public changeset
                     succs.update(obsolete.allsuccessors(repo.obsstore,
                                                         [c.node()]))
-            validdests = set(repo.set('%ln::', succs))
+            known = (n for n in succs if nm.get(n) is not None)
+            validdests = set(repo.set('%ln::', known))
         validdests.remove(old)
         return new in validdests
     else:
diff --git a/tests/test-bookmarks-pushpull.t b/tests/test-bookmarks-pushpull.t
--- a/tests/test-bookmarks-pushpull.t
+++ b/tests/test-bookmarks-pushpull.t
@@ -262,7 +262,8 @@ Update to a successor works
   4efff6d98829d9c824c621afd6e3f01865f5439f
   $ hg id --debug -r 5
   c922c0139ca03858f655e4a2af4dd02796a63969 tip Y
-  $ hg debugobsolete f6fc62dde3c0771e29704af56ba4d8af77abcc2f 4efff6d98829d9c824c621afd6e3f01865f5439f
+  $ hg debugobsolete f6fc62dde3c0771e29704af56ba4d8af77abcc2f cccccccccccccccccccccccccccccccccccccccc
+  $ hg debugobsolete cccccccccccccccccccccccccccccccccccccccc 4efff6d98829d9c824c621afd6e3f01865f5439f
   $ hg push http://localhost:$HGPORT2/
   pushing to http://localhost:$HGPORT2/
   searching for changes