diff --git a/mercurial/discovery.py b/mercurial/discovery.py
--- a/mercurial/discovery.py
+++ b/mercurial/discovery.py
@@ -153,7 +153,10 @@ def checkheads(repo, remote, outgoing, r
         branches = set(repo[n].branch() for n in outgoing.missing)
 
         # 2. Check for new branches on the remote.
-        remotemap = remote.branchmap()
+        if remote.local():
+            remotemap = phases.visiblebranchmap(remote)
+        else:
+            remotemap = remote.branchmap()
         newbranches = branches - set(remotemap)
         if newbranches and not newbranch: # new branch requires --new-branch
             branchnames = ', '.join(sorted(newbranches))
diff --git a/mercurial/phases.py b/mercurial/phases.py
--- a/mercurial/phases.py
+++ b/mercurial/phases.py
@@ -263,6 +263,28 @@ def visibleheads(repo):
         vheads = repo.heads()
     return vheads
 
+def visiblebranchmap(repo):
+    """return a branchmap for the visible set"""
+    # XXX Recomputing this data on the fly is very slow.  We should build a
+    # XXX cached version while computin the standard branchmap version.
+    sroots = repo._phaseroots[secret]
+    if sroots:
+        vbranchmap = {}
+        for branch, nodes in  repo.branchmap().iteritems():
+            # search for secret heads.
+            for n in nodes:
+                if repo[n].phase() >= secret:
+                    nodes = None
+                    break
+            # if secreat heads where found we must compute them again
+            if nodes is None:
+                s = repo.set('heads(branch(%s) - secret())', branch)
+                nodes = [c.node() for c in s]
+            vbranchmap[branch] = nodes
+    else:
+        vbranchmap = repo.branchmap()
+    return vbranchmap
+
 def analyzeremotephases(repo, subset, roots):
     """Compute phases heads and root in a subset of node from root dict
 
diff --git a/mercurial/wireproto.py b/mercurial/wireproto.py
--- a/mercurial/wireproto.py
+++ b/mercurial/wireproto.py
@@ -396,7 +396,7 @@ def between(repo, proto, pairs):
     return "".join(r)
 
 def branchmap(repo, proto):
-    branchmap = repo.branchmap()
+    branchmap = phases.visiblebranchmap(repo)
     heads = []
     for branch, nodes in branchmap.iteritems():
         branchname = urllib.quote(encoding.fromlocal(branch))
diff --git a/tests/test-phases-exchange.t b/tests/test-phases-exchange.t
--- a/tests/test-phases-exchange.t
+++ b/tests/test-phases-exchange.t
@@ -833,12 +833,20 @@ Discovery locally secret changeset on a 
   o  0 public a-A - 054250a37db4
   
 
-pushing a locally public and draft changesets remotly secret should make them appear on the remote side
+pushing a locally public and draft changesets remotly secret should make them
+appear on the remote side.
+
 
   $ hg -R ../mu phase --secret --force 967b449fbc94
   $ hg push -r 435b5d83910c ../mu
   pushing to ../mu
   searching for changes
+  abort: push creates new remote head 435b5d83910c!
+  (did you forget to merge? use push -f to force)
+  [255]
+  $ hg push -fr 435b5d83910c ../mu # because the push will create new visible head
+  pushing to ../mu
+  searching for changes
   adding changesets
   adding manifests
   adding file changes
diff --git a/tests/test-phases.t b/tests/test-phases.t
--- a/tests/test-phases.t
+++ b/tests/test-phases.t
@@ -135,6 +135,39 @@ Test secret changeset are not pushed
   2 1 C
   1 0 B
   0 0 A
+
+(Issue3303)
+Check that remote secret changeset are ignore when checking creation of remote heads
+
+We add a secret head into the push destination.  This secreat head shadow a
+visible shared between the initial repo and the push destination.
+
+  $ hg up -q 4 # B'
+  $ mkcommit Z --config phases.new-commit=secret
+  $ hg phase .
+  5: secret
+
+# We now try to push a new public changeset that descend from the common public
+# head shadowed by the remote secret head.
+
+  $ cd ../initialrepo
+  $ hg up -q 6 #B'
+  $ mkcommit I
+  created new head
+  $ hg push ../push-dest
+  pushing to ../push-dest
+  searching for changes
+  adding changesets
+  adding manifests
+  adding file changes
+  added 1 changesets with 1 changes to 1 files (+1 heads)
+
+:note: The "(+1 heads)" is wrong as we do not had any visible head
+
+
+Restore condition prior extra insertion.
+  $ hg -q --config extensions.mq= strip .
+  $ hg up -q 7
   $ cd ..
 
 Test secret changeset are not pull