diff --git a/mercurial/discovery.py b/mercurial/discovery.py
--- a/mercurial/discovery.py
+++ b/mercurial/discovery.py
@@ -7,7 +7,7 @@
 
 from node import nullid, short
 from i18n import _
-import util, setdiscovery, treediscovery, phases
+import util, setdiscovery, treediscovery, phases, obsolete
 
 def findcommonincoming(repo, remote, heads=None, force=False):
     """Return a tuple (common, anyincoming, heads) used to identify the common
@@ -266,6 +266,7 @@ def checkheads(repo, remote, outgoing, r
     # error message, depending on unsynced status, is displayed.
     error = None
     unsynced = False
+    allmissing = set(outgoing.missing)
     for branch, heads in headssum.iteritems():
         if heads[0] is None:
             # Maybe we should abort if we push more that one head
@@ -274,8 +275,34 @@ def checkheads(repo, remote, outgoing, r
         if heads[2]:
             unsynced = True
         oldhs = set(heads[0])
-        newhs = set(heads[1])
+        candidate_newhs = set(heads[1])
+        # add unsynced data
+        oldhs.update(heads[2])
+        candidate_newhs.update(heads[2])
         dhs = None
+        if repo.obsstore:
+            # remove future heads which are actually obsolete by another
+            # pushed element:
+            #
+            # XXX There is several case this case does not handle properly
+            #
+            # (1) if <nh> is public, it won't be affected by obsolete marker
+            #     and a new is created
+            #
+            # (2) if the new heads have ancestors which are not obsolete and
+            #     not ancestors of any other heads we will have a new head too.
+            #
+            # This two case will be easy to handle for know changeset but much
+            # more tricky for unsynced changes.
+            newhs = set()
+            for nh in candidate_newhs:
+                for suc in obsolete.anysuccessors(repo.obsstore, nh):
+                    if suc != nh and suc in allmissing:
+                        break
+                else:
+                    newhs.add(nh)
+        else:
+            newhs = candidate_newhs
         if len(newhs) > len(oldhs):
             # strip updates to existing remote heads from the new heads list
             dhs = list(newhs - bookmarkedheads - oldhs)
diff --git a/tests/test-obsolete.t b/tests/test-obsolete.t
--- a/tests/test-obsolete.t
+++ b/tests/test-obsolete.t
@@ -357,3 +357,50 @@ no warning displayed
   searching for changes
   no changes found
   [1]
+
+Do not warn about new head when the new head is a successors of a remote one
+
+  $ hg glog
+  @  changeset:   5:6e572121998e
+  |  tag:         tip
+  |  user:        test
+  |  date:        Thu Jan 01 00:00:00 1970 +0000
+  |  summary:     add original_e
+  |
+  x  changeset:   4:7c694bff0650
+  |  user:        test
+  |  date:        Thu Jan 01 00:00:00 1970 +0000
+  |  summary:     add original_d
+  |
+  o  changeset:   3:5601fb93a350
+  |  parent:      1:7c3bad9141dc
+  |  user:        test
+  |  date:        Thu Jan 01 00:00:00 1970 +0000
+  |  summary:     add new_3_c
+  |
+  | o  changeset:   2:245bde4270cd
+  |/   user:        test
+  |    date:        Thu Jan 01 00:00:00 1970 +0000
+  |    summary:     add original_c
+  |
+  o  changeset:   1:7c3bad9141dc
+  |  user:        test
+  |  date:        Thu Jan 01 00:00:00 1970 +0000
+  |  summary:     add b
+  |
+  o  changeset:   0:1f0dee641bb7
+     user:        test
+     date:        Thu Jan 01 00:00:00 1970 +0000
+     summary:     add a
+  
+  $ hg up -q 'desc(new_3_c)'
+  $ mkcommit obsolete_e
+  created new head
+  $ hg debugobsolete `getid 'original_e'` `getid 'obsolete_e'`
+  $ hg push ../tmpf
+  pushing to ../tmpf
+  searching for changes
+  adding changesets
+  adding manifests
+  adding file changes
+  added 1 changesets with 1 changes to 1 files (+1 heads)