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-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