diff --git a/mercurial/commands.py b/mercurial/commands.py
--- a/mercurial/commands.py
+++ b/mercurial/commands.py
@@ -766,9 +766,37 @@ def commit(ui, repo, *pats, **opts):
     ctx = repo[node]
     parents = ctx.parents()
 
-    if bheads and [x for x in parents
-                   if x.node() not in bheads and x.branch() == branch]:
+    if bheads and not [x for x in parents
+                       if x.node() in bheads and x.branch() == branch]:
         ui.status(_('created new head\n'))
+        # The message is not printed for initial roots. For the other
+        # changesets, it is printed in the following situations:
+        #
+        # Par column: for the 2 parents with ...
+        #   N: null or no parent
+        #   B: parent is on another named branch
+        #   C: parent is a regular non head changeset
+        #   H: parent was a branch head of the current branch
+        # Msg column: whether we print "created new head" message
+        # In the following, it is assumed that there already exists some
+        # initial branch heads of the current branch, otherwise nothing is
+        # printed anyway.
+        #
+        # Par Msg Comment
+        # NN   y  additional topo root
+        #
+        # BN   y  additional branch root
+        # CN   y  additional topo head
+        # HN   n  usual case
+        #
+        # BB   y  weird additional branch root
+        # CB   y  branch merge
+        # HB   n  merge with named branch
+        #
+        # CC   y  additional head from merge
+        # CH   n  merge with a head
+        #
+        # HH   n  head merge: head count decreases
 
     if not opts.get('close_branch'):
         for r in parents:
diff --git a/tests/test-backout.out b/tests/test-backout.out
--- a/tests/test-backout.out
+++ b/tests/test-backout.out
@@ -73,6 +73,7 @@ adding file1
 marked working directory as branch branch2
 adding file2
 removing file1
+created new head
 changeset 3:d4e8f6db59fb backs out changeset 1:bf1602f437f3
 the backout changeset is a new head - do not forget to merge
 (use "backout --merge" if you want to auto-merge)
diff --git a/tests/test-branch-option.out b/tests/test-branch-option.out
--- a/tests/test-branch-option.out
+++ b/tests/test-branch-option.out
@@ -17,6 +17,7 @@ 1 files updated, 0 files merged, 0 files
 marked working directory as branch æ
 1 files updated, 0 files merged, 0 files removed, 0 files unresolved
 marked working directory as branch b
+created new head
 in rev c branch a
 1:dd6e60a716c6
 2:f25d57ab0566
diff --git a/tests/test-fetch.out b/tests/test-fetch.out
--- a/tests/test-fetch.out
+++ b/tests/test-fetch.out
@@ -182,6 +182,7 @@ marked working directory as branch secon
 adding b
 marked working directory as branch default
 adding c
+created new head
 updating to branch default
 3 files updated, 0 files merged, 0 files removed, 0 files unresolved
 % fetch should succeed
diff --git a/tests/test-newbranch.out b/tests/test-newbranch.out
--- a/tests/test-newbranch.out
+++ b/tests/test-newbranch.out
@@ -4,6 +4,7 @@ marked working directory as branch bar
 % branch shadowing
 abort: a branch of the same name already exists (use 'hg update' to switch to it)
 marked working directory as branch default
+created new head
 % there should be only one default branch head
 changeset:   3:bf1bc2f45e83
 tag:         tip
diff --git a/tests/test-push-warn.out b/tests/test-push-warn.out
--- a/tests/test-push-warn.out
+++ b/tests/test-push-warn.out
@@ -279,8 +279,10 @@ updating to branch B
 1 files updated, 0 files merged, 0 files removed, 0 files unresolved
 1 files updated, 0 files merged, 1 files removed, 0 files unresolved
 marked working directory as branch B
+created new head
 1 files updated, 0 files merged, 1 files removed, 0 files unresolved
 marked working directory as branch A
+created new head
 %% glog of local
 @  5: A b3
 |
diff --git a/tests/test-subrepo.out b/tests/test-subrepo.out
--- a/tests/test-subrepo.out
+++ b/tests/test-subrepo.out
@@ -90,7 +90,6 @@ path t
  source   t
  revision 6747d179aa9a688023c4b0cad32e4c92bb7f34ad
 committing subrepository t
-created new head
   searching for copies back to rev 2
 resolving manifests
  overwrite None partial False