diff --git a/hgext3rd/pushrebase.py b/hgext3rd/pushrebase.py
--- a/hgext3rd/pushrebase.py
+++ b/hgext3rd/pushrebase.py
@@ -39,7 +39,7 @@
     hg,
     manifest,
     obsolete,
-    phases,
+    phases as phasesmod,
     pushkey,
     registrar,
     revsetlang,
@@ -127,6 +127,12 @@
     bundle2.parthandlermapping['pushkey'] = newpushkeyhandler
     bundle2.parthandlermapping['b2x:pushkey'] = newpushkeyhandler
 
+    origphaseheadshandler = bundle2.parthandlermapping['phase-heads']
+    newphaseheadshandler = lambda *args, **kwargs: \
+        bundle2phaseheads(origphaseheadshandler, *args, **kwargs)
+    newphaseheadshandler.params = origphaseheadshandler.params
+    bundle2.parthandlermapping['phase-heads'] = newphaseheadshandler
+
     wrapfunction(exchange, 'unbundle', unbundle)
 
     wrapfunction(hg, '_peerorrepo', _peerorrepo)
@@ -349,7 +355,7 @@
                 self._pushrebasereplaces[prec] = sucs[0]
     return orig(self, transaction, data)
 
-def _phasemove(orig, pushop, nodes, phase=phases.public):
+def _phasemove(orig, pushop, nodes, phase=phasesmod.public):
     """prevent original changesets from being marked public
 
     When marking changesets as public, we need to mark the replaced nodes
@@ -386,7 +392,7 @@
     # is not enabled locally.
     mapping = getattr(pushop.repo.obsstore, '_pushrebasereplaces', {})
     nodes = [mapping.get(n, n) for n in nodes]
-    if phase == phases.public:
+    if phase == phasesmod.public:
         # only allow new nodes to become public
         allowednodes = set(mapping.values())
         nodes = [n for n in nodes if n in allowednodes]
@@ -845,7 +851,7 @@
     # Move public phase forward
     publishing = op.repo.ui.configbool('phases', 'publish', untrusted=True)
     if publishing:
-        phases.advanceboundary(op.repo, tr, phases.public, [added[-1]])
+        phasesmod.advanceboundary(op.repo, tr, phasesmod.public, [added[-1]])
 
     addfinalhooks(op, tr, hookargs, added)
 
@@ -1011,6 +1017,8 @@
                     lambda tr: op.repo._afterlock(runhooks))
 
 def bundle2pushkey(orig, op, part):
+    # Merges many dicts into one. First it converts them to list of pairs,
+    # then concatenates them (using sum), and then creates a diff out of them.
     replacements = dict(sum([record.items()
                              for record
                              in op.records[rebaseparttype]],
@@ -1041,3 +1049,24 @@
                 part.params['old'] = pushkey.encode(hex(serverbin))
 
     return orig(op, part)
+
+def bundle2phaseheads(orig, op, part):
+    # Merges many dicts into one. First it converts them to list of pairs,
+    # then concatenates them (using sum), and then creates a diff out of them.
+    replacements = dict(sum([record.items()
+                             for record
+                             in op.records[rebaseparttype]],
+                            []))
+
+    decodedphases = phasesmod.binarydecode(part)
+
+    replacedphases = []
+    for phasetype in decodedphases:
+        replacedphases.append(
+            [replacements.get(node, node) for node in phasetype])
+    # Since we've just read the bundle part, then `orig()` won't be able to
+    # read it again. Let's replace payload stream with new stream of replaced
+    # nodes.
+    part._payloadstream = util.chunkbuffer(
+        [phasesmod.binaryencode(replacedphases)])
+    return orig(op, part)
diff --git a/tests/test-pushrebase.t b/tests/test-pushrebase.t
--- a/tests/test-pushrebase.t
+++ b/tests/test-pushrebase.t
@@ -622,7 +622,6 @@
       11be4ca7f3f4  second
       a5e72ac0df88  last
   pretxnchangegroup hook: HG_BUNDLE2=1 HG_HOOKNAME=pretxnchangegroup HG_HOOKTYPE=pretxnchangegroup HG_NODE=4fcee35c508c1019667f72cae9b843efa8908701 HG_NODE_LAST=a5e72ac0df8881afef34132987e8ae78d2e6cb13 HG_PENDING=$TESTTMP/hookserver HG_SOURCE=push HG_TXNID=TXN:* HG_URL=file:$TESTTMP/hookserver (glob)
-  prepushkey hook: HG_BUNDLE2=1 HG_HOOKNAME=prepushkey HG_HOOKTYPE=prepushkey HG_KEY=a5e72ac0df8881afef34132987e8ae78d2e6cb13 HG_NAMESPACE=phases HG_NEW=0 HG_NODE=4fcee35c508c1019667f72cae9b843efa8908701 HG_OLD=1 HG_PENDING=$TESTTMP/hookserver HG_PHASES_MOVED=1 HG_SOURCE=push HG_TXNID=TXN:* HG_URL=file:$TESTTMP/hookserver (glob)
   prepushkey hook: HG_BUNDLE2=1 HG_HOOKNAME=prepushkey HG_HOOKTYPE=prepushkey HG_KEY=master HG_NAMESPACE=bookmarks HG_NEW=a5e72ac0df8881afef34132987e8ae78d2e6cb13 HG_NODE=4fcee35c508c1019667f72cae9b843efa8908701 HG_OLD=e95be919ac60f0c114075e32a0a4301afabadb60 HG_PENDING=$TESTTMP/hookserver HG_PHASES_MOVED=1 HG_SOURCE=push HG_TXNID=TXN:* HG_URL=file:$TESTTMP/hookserver (glob)
   pretxnclose hook: HG_BOOKMARK_MOVED=1 HG_BUNDLE2=1 HG_HOOKNAME=pretxnclose HG_HOOKTYPE=pretxnclose HG_NODE=4fcee35c508c1019667f72cae9b843efa8908701 HG_PENDING=$TESTTMP/hookserver HG_PHASES_MOVED=1 HG_SOURCE=push HG_TXNID=TXN:* HG_TXNNAME=push HG_URL=file:$TESTTMP/hookserver (glob)
   txnclose hook: HG_BOOKMARK_MOVED=1 HG_BUNDLE2=1 HG_HOOKNAME=txnclose HG_HOOKTYPE=txnclose HG_NODE=4fcee35c508c1019667f72cae9b843efa8908701 HG_PHASES_MOVED=1 HG_SOURCE=push HG_TXNID=TXN:* HG_TXNNAME=push HG_URL=file:$TESTTMP/hookserver (glob)