diff --git a/mercurial/discovery.py b/mercurial/discovery.py
--- a/mercurial/discovery.py
+++ b/mercurial/discovery.py
@@ -341,6 +341,10 @@ def checkheads(repo, remote, outgoing, r
                 if branch not in ('default', None):
                     error = _("push creates new remote head %s "
                               "on branch '%s'!") % (short(dhs[0]), branch)
+                elif repo[dhs[0]].bookmarks():
+                    error = _("push creates new remote head %s "
+                              "with bookmark '%s'!") % (
+                              short(dhs[0]), repo[dhs[0]].bookmarks()[0])
                 else:
                     error = _("push creates new remote head %s!"
                               ) % short(dhs[0])
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
@@ -274,7 +274,7 @@ diverging a remote bookmark fails
   $ hg push http://localhost:$HGPORT2/
   pushing to http://localhost:$HGPORT2/
   searching for changes
-  abort: push creates new remote head c922c0139ca0!
+  abort: push creates new remote head c922c0139ca0 with bookmark 'Y'!
   (merge or see "hg help push" for details about pushing new heads)
   [255]
   $ hg -R ../a book
@@ -290,7 +290,7 @@ Unrelated marker does not alter the deci
   $ hg push http://localhost:$HGPORT2/
   pushing to http://localhost:$HGPORT2/
   searching for changes
-  abort: push creates new remote head c922c0139ca0!
+  abort: push creates new remote head c922c0139ca0 with bookmark 'Y'!
   (merge or see "hg help push" for details about pushing new heads)
   [255]
   $ hg -R ../a book