diff --git a/mercurial/discovery.py b/mercurial/discovery.py
--- a/mercurial/discovery.py
+++ b/mercurial/discovery.py
@@ -268,7 +268,6 @@ def checkheads(repo, remote, outgoing, r
     # If there are more heads after the push than before, a suitable
     # error message, depending on unsynced status, is displayed.
     error = None
-    unsynced = False
     allmissing = set(outgoing.missing)
     allfuturecommon = set(c.node() for c in repo.set('%ld', outgoing.common))
     allfuturecommon.update(allmissing)
@@ -312,8 +311,15 @@ def checkheads(repo, remote, outgoing, r
                         newhs.add(nh)
         else:
             newhs = candidate_newhs
-        if [h for h in unsyncedheads if h not in discardedheads]:
-            unsynced = True
+        unsynced = sorted(h for h in unsyncedheads if h not in discardedheads)
+        if unsynced:
+            heads = ' '.join(short(h) for h in unsynced)
+            if branch is None:
+                repo.ui.warn(_("remote has heads that are "
+                               "not known locally: %s\n") % heads)
+            else:
+                repo.ui.warn(_("remote has heads on branch '%s' that are "
+                               "not known locally: %s\n") % (branch, heads))
         if remoteheads is None:
             if len(newhs) > 1:
                 dhs = list(newhs)
@@ -350,7 +356,3 @@ def checkheads(repo, remote, outgoing, r
                 repo.ui.note((" %s\n") % short(h))
     if error:
         raise util.Abort(error, hint=hint)
-
-    # 6. Check for unsynced changes on involved branches.
-    if unsynced:
-        repo.ui.warn(_("note: unsynced remote changes!\n"))
diff --git a/tests/test-push-warn.t b/tests/test-push-warn.t
--- a/tests/test-push-warn.t
+++ b/tests/test-push-warn.t
@@ -22,6 +22,7 @@
   $ hg push ../a
   pushing to ../a
   searching for changes
+  remote has heads on branch 'default' that are not known locally: 1c9246a22a0a
   abort: push creates new remote head 1e108cc5548c!
   (pull and merge or see "hg help push" for details about pushing new heads)
   [255]
@@ -35,6 +36,7 @@
   query 2; still undecided: 1, sample size is: 1
   2 total queries
   listing keys for "bookmarks"
+  remote has heads on branch 'default' that are not known locally: 1c9246a22a0a
   new remote heads on branch 'default':
    1e108cc5548c
   abort: push creates new remote head 1e108cc5548c!
@@ -405,6 +407,7 @@ multiple new heads:
   $ hg -R i push h
   pushing to h
   searching for changes
+  remote has heads on branch 'default' that are not known locally: ce4212fc8847
   abort: push creates new remote head 97bd0c84d346!
   (pull and merge or see "hg help push" for details about pushing new heads)
   [255]
diff --git a/tests/test-ssh.t b/tests/test-ssh.t
--- a/tests/test-ssh.t
+++ b/tests/test-ssh.t
@@ -223,7 +223,7 @@ push should succeed even though it has a
   $ hg push
   pushing to ssh://user@dummy/remote
   searching for changes
-  note: unsynced remote changes!
+  remote has heads on branch 'default' that are not known locally: 6c0482d977a3
   remote: adding changesets
   remote: adding manifests
   remote: adding file changes