diff --git a/mercurial/exchange.py b/mercurial/exchange.py
--- a/mercurial/exchange.py
+++ b/mercurial/exchange.py
@@ -226,10 +226,6 @@ def push(repo, remote, force=False, revs
         if locallock is not None:
             locallock.release()
 
-    if pushop.bookmarks:
-        pushop.bkresult = bookmod.pushtoremote(repo.ui, repo, remote,
-                                               pushop.bookmarks)
-
     return pushop
 
 # list of steps to perform discovery before push
@@ -334,11 +330,40 @@ def _pushdiscoverybookmarks(pushop):
         ancestors = repo.changelog.ancestors(revnums, inclusive=True)
     remotebookmark = remote.listkeys('bookmarks')
 
+    explicit = set(pushop.bookmarks)
+
     comp = bookmod.compare(repo, repo._bookmarks, remotebookmark, srchex=hex)
     addsrc, adddst, advsrc, advdst, diverge, differ, invalid = comp
     for b, scid, dcid in advsrc:
+        if b in explicit:
+            explicit.remove(b)
         if not ancestors or repo[scid].rev() in ancestors:
             pushop.outbookmarks.append((b, dcid, scid))
+    # search added bookmark
+    for b, scid, dcid in addsrc:
+        if b in explicit:
+            explicit.remove(b)
+            pushop.outbookmarks.append((b, '', scid))
+    # search for overwritten bookmark
+    for b, scid, dcid in advdst + diverge + differ:
+        if b in explicit:
+            explicit.remove(b)
+            pushop.outbookmarks.append((b, dcid, scid))
+    # search for bookmark to delete
+    for b, scid, dcid in adddst:
+        if b in explicit:
+            explicit.remove(b)
+            # treat as "deleted locally"
+            pushop.outbookmarks.append((b, dcid, ''))
+
+    if explicit:
+        explicit = sorted(explicit)
+        # we should probably list all of them
+        ui.warn(_('bookmark %s does not exist on the local '
+                  'or remote repository!\n') % explicit[0])
+        pushop.bkresult = 2
+
+    pushop.outbookmarks.sort()
 
 def _pushcheckoutgoing(pushop):
     outgoing = pushop.outgoing
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
@@ -99,8 +99,8 @@ push/pull name that doesn't exist
   $ hg push -B badname ../a
   pushing to ../a
   searching for changes
+  bookmark badname does not exist on the local or remote repository!
   no changes found
-  bookmark badname does not exist on the local or remote repository!
   [2]
   $ hg pull -B anotherbadname ../a
   pulling from ../a
@@ -356,7 +356,7 @@ hgweb
   pushing to http://localhost:$HGPORT/
   searching for changes
   no changes found
-  exporting bookmark Z
+  updating bookmark Z
   [1]
   $ hg book -d Z
   $ hg in -B http://localhost:$HGPORT/
diff --git a/tests/test-bundle2.t b/tests/test-bundle2.t
--- a/tests/test-bundle2.t
+++ b/tests/test-bundle2.t
@@ -881,7 +881,6 @@ push
   remote: added 1 changesets with 0 changes to 0 files (-1 heads)
   remote: 1 new obsolescence markers
   updating bookmark book_eea1
-  exporting bookmark book_eea1
   $ hg -R other log -G
   o    3:eea13746799a public Nicolas Dumazet <nicdumz.commits@gmail.com> book_eea1 G
   |\
@@ -950,7 +949,6 @@ push over ssh
   remote: added 1 changesets with 1 changes to 1 files
   remote: 1 new obsolescence markers
   updating bookmark book_5fdd
-  exporting bookmark book_5fdd
   $ hg -R other log -G
   o  6:5fddd98957c8 draft Nicolas Dumazet <nicdumz.commits@gmail.com> book_5fdd C
   |
@@ -989,7 +987,6 @@ push over http
   remote: added 1 changesets with 1 changes to 1 files
   remote: 1 new obsolescence markers
   updating bookmark book_32af
-  exporting bookmark book_32af
   $ cat other-error.log
 
 Check final content.
diff --git a/tests/test-hook.t b/tests/test-hook.t
--- a/tests/test-hook.t
+++ b/tests/test-hook.t
@@ -183,8 +183,8 @@ pushkey hook
   pushing to ../a
   searching for changes
   no changes found
+  pushkey hook: HG_KEY=foo HG_NAMESPACE=bookmarks HG_NEW=0000000000000000000000000000000000000000 HG_RET=1
   exporting bookmark foo
-  pushkey hook: HG_KEY=foo HG_NAMESPACE=bookmarks HG_NEW=0000000000000000000000000000000000000000 HG_RET=1
   [1]
   $ cd ../a
 
@@ -215,8 +215,6 @@ test that prepushkey can prevent incomin
   listkeys hook: HG_NAMESPACE=bookmarks HG_VALUES={'bar': '0000000000000000000000000000000000000000', 'foo': '0000000000000000000000000000000000000000'}
   no changes found
   listkeys hook: HG_NAMESPACE=phases HG_VALUES={'cb9a9f314b8b07ba71012fcdbc544b5a4d82ff5b': '1', 'publishing': 'True'}
-  listkeys hook: HG_NAMESPACE=bookmarks HG_VALUES={'bar': '0000000000000000000000000000000000000000', 'foo': '0000000000000000000000000000000000000000'}
-  exporting bookmark baz
   prepushkey.forbid hook: HG_KEY=baz HG_NAMESPACE=bookmarks HG_NEW=0000000000000000000000000000000000000000
   abort: prepushkey hook exited with status 1
   [255]