diff --git a/mercurial/commands.py b/mercurial/commands.py
--- a/mercurial/commands.py
+++ b/mercurial/commands.py
@@ -4677,6 +4677,7 @@ def push(ui, repo, dest=None, **opts):
     """
 
     if opts.get('bookmark'):
+        ui.setconfig('bookmarks', 'pushing', opts['bookmark'])
         for b in opts['bookmark']:
             # translate -B options to -r so changesets get pushed
             if b in repo._bookmarks:
diff --git a/mercurial/discovery.py b/mercurial/discovery.py
--- a/mercurial/discovery.py
+++ b/mercurial/discovery.py
@@ -219,7 +219,8 @@ def _oldheadssummary(repo, remoteheads, 
     unsynced = inc and set([None]) or set()
     return {None: (oldheads, newheads, unsynced)}
 
-def checkheads(repo, remote, outgoing, remoteheads, newbranch=False, inc=False):
+def checkheads(repo, remote, outgoing, remoteheads, newbranch=False, inc=False,
+               newbookmarks=[]):
     """Check that a push won't add any outgoing head
 
     raise Abort error and display ui message as needed.
@@ -259,6 +260,9 @@ def checkheads(repo, remote, outgoing, r
             lctx, rctx = repo[bm], repo[rnode]
             if bookmarks.validdest(repo, rctx, lctx):
                 bookmarkedheads.add(lctx.node())
+        else:
+            if bm in newbookmarks:
+                bookmarkedheads.add(repo[bm].node())
 
     # 3. Check for new heads.
     # If there are more heads after the push than before, a suitable
diff --git a/mercurial/localrepo.py b/mercurial/localrepo.py
--- a/mercurial/localrepo.py
+++ b/mercurial/localrepo.py
@@ -1867,9 +1867,10 @@ class localrepository(object):
                                     raise util.Abort(_(mst)
                                                      % (ctx.troubles()[0],
                                                         ctx))
+                        newbm = self.ui.configlist('bookmarks', 'pushing')
                         discovery.checkheads(unfi, remote, outgoing,
                                              remoteheads, newbranch,
-                                             bool(inc))
+                                             bool(inc), newbm)
 
                     # TODO: get bundlecaps from remote
                     bundlecaps = None
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
@@ -424,4 +424,22 @@ of this test.
   remote: added 1 changesets with 1 changes to 1 files
   exporting bookmark add-foo
 
+pushing a new bookmark on a new head does not require -f if -B is specified
+
+  $ hg up -q X
+  $ hg book W
+  $ echo c5 > f2
+  $ hg ci -Am5
+  created new head
+  $ hg push -B W
+  pushing to http://localhost:$HGPORT/
+  searching for changes
+  remote: adding changesets
+  remote: adding manifests
+  remote: adding file changes
+  remote: added 1 changesets with 1 changes to 1 files (+1 heads)
+  exporting bookmark W
+  $ hg -R ../b id -r W
+  cc978a373a53 tip W
+
   $ cd ..