diff --git a/mercurial/localrepo.py b/mercurial/localrepo.py
--- a/mercurial/localrepo.py
+++ b/mercurial/localrepo.py
@@ -1632,21 +1632,60 @@ class localrepository(repo.repository):
                     # XXX If push failed we should use strict common and not
                     # future to avoir pushing phase data on unknown changeset.
                     # This is to done later.
-                    futctx = [self[n] for n in fut if n != nullid]
-                    for phase in phases.trackedphases[::-1]:
-                        prevphase = phase -1
-                        # get all candidate for head in previous phase
-                        inprev = [ctx for ctx in futctx
-                                      if ctx.phase() == prevphase]
-                        for newremotehead in  self.set('heads(%ld & (%ln::))',
-                                              inprev, rroots[phase]):
-                            r = remote.pushkey('phases',
-                                               newremotehead.hex(),
-                                               str(phase), str(prevphase))
-                            if not r:
-                                self.ui.warn(_('updating phase of %s'
-                                               'to %s failed!\n')
-                                                % (newremotehead, prevphase))
+
+                    # element we want to push
+                    topush = []
+
+                    # store details of known remote phase of several revision
+                    # /!\ set of index I holds rev where: I <= rev.phase()
+                    # /!\ public phase (index 0) is ignored
+                    remdetails = [set() for i in xrange(len(phases.allphases))]
+                    _revs = set()
+                    for relremphase in phases.trackedphases[::-1]:
+                        # we iterate backward because the list alway grows
+                        # when filled in this direction.
+                        _revs.update(self.revs('%ln::%ln',
+                                               rroots[relremphase], fut))
+                        remdetails[relremphase].update(_revs)
+
+                    for phase in phases.allphases[:-1]:
+                        # We don't need the last phase as we will never want to
+                        # move anything to it while moving phase backward.
+
+                        # Get the list of all revs on remote which are in a
+                        # phase higher than currently processed phase.
+                        relremrev = remdetails[phase + 1]
+
+                        if not relremrev:
+                            # no candidate to remote push anymore
+                            # break before any expensive revset
+                            break
+
+                        #dynamical inject appropriate phase symbol
+                        phasename = phases.phasenames[phase]
+                        odrevset = 'heads(%%ld and %s())' % phasename
+                        outdated =  self.set(odrevset, relremrev)
+                        for od in outdated:
+                            candstart = len(remdetails) - 1
+                            candstop = phase + 1
+                            candidateold = xrange(candstart, candstop, -1)
+                            for oldphase in candidateold:
+                                if od.rev() in remdetails[oldphase]:
+                                    break
+                            else: # last one: no need to search
+                                oldphase = phase + 1
+                            topush.append((oldphase, phase, od))
+
+                    # push every needed data
+                    for oldphase, newphase, newremotehead in topush:
+                        r = remote.pushkey('phases',
+                                           newremotehead.hex(),
+                                           str(oldphase), str(newphase))
+                        if not r:
+                            self.ui.warn(_('updating phase of %s '
+                                           'to %s from %s failed!\n')
+                                            % (newremotehead, newphase,
+                                               oldphase))
             finally:
                 locallock.release()
         finally:
diff --git a/tests/test-phases.t b/tests/test-phases.t
--- a/tests/test-phases.t
+++ b/tests/test-phases.t
@@ -91,6 +91,10 @@ Even on merge
 Test secret changeset are not pushed
 
   $ hg init ../push-dest
+  $ cat > ../push-dest/.hg/hgrc << EOF
+  > [phases]
+  > publish=False
+  > EOF
   $ hg push ../push-dest -f # force because we push multiple heads
   pushing to ../push-dest
   searching for changes
@@ -100,18 +104,18 @@ Test secret changeset are not pushed
   added 5 changesets with 5 changes to 5 files (+1 heads)
   $ hglog
   7 2 merge B' and E
-  6 0 B'
+  6 1 B'
   5 2 H
   4 2 E
-  3 0 D
-  2 0 C
+  3 1 D
+  2 1 C
   1 0 B
   0 0 A
   $ cd ../push-dest
   $ hglog
-  4 0 B'
-  3 0 D
-  2 0 C
+  4 1 B'
+  3 1 D
+  2 1 C
   1 0 B
   0 0 A
   $ cd ..
@@ -142,10 +146,10 @@ Test revset
   $ hglog -r 'public()'
   0 0 A
   1 0 B
-  2 0 C
-  3 0 D
-  6 0 B'
   $ hglog -r 'draft()'
+  2 1 C
+  3 1 D
+  6 1 B'
   $ hglog -r 'secret()'
   4 2 E
   5 2 H
diff --git a/tests/test-push-http.t b/tests/test-push-http.t
--- a/tests/test-push-http.t
+++ b/tests/test-push-http.t
@@ -29,7 +29,7 @@ expect ssl error
   searching for changes
   remote: ssl required
   remote: ssl required
-  updating phase of ba677d0156c1to 0 failed!
+  updating phase of ba677d0156c1 to 0 from 1 failed!
   % serve errors
 
 expect authorization error