diff --git a/mercurial/phases.py b/mercurial/phases.py
--- a/mercurial/phases.py
+++ b/mercurial/phases.py
@@ -266,7 +266,15 @@ class phasecache(object):
                 filtered = True
         if filtered:
             self.dirty = True
-            self._phaserevs = None
+        # filterunknown is called by repo.destroyed, we may have no changes in
+        # root but phaserevs contents is certainly invalide (or at least we
+        # have not proper way to check that. related to issue 3858.
+        #
+        # The other caller is __init__ that have no _phaserevs initialized
+        # anyway. If this change we should consider adding a dedicated
+        # "destroyed" function to phasecache or a proper cache key mechanisme
+        # (see branchmap one)
+        self._phaserevs = None
 
 def advanceboundary(repo, targetphase, nodes):
     """Add nodes to a phase changing other nodes phases if necessary.
diff --git a/tests/test-rebase-cache.t b/tests/test-rebase-cache.t
--- a/tests/test-rebase-cache.t
+++ b/tests/test-rebase-cache.t
@@ -385,3 +385,112 @@ Try both orders.
 
   $ hg theads
   0: 'A' 
+
+Make sure rebase does not break for phase/filter related reason
+----------------------------------------------------------------
+(issue3858)
+
+  $ cd ..
+
+  $ cat >> $HGRCPATH << EOF
+  > [ui]
+  > logtemplate={rev} {desc} {phase}\n
+  > EOF
+  $ cat $HGRCPATH
+  [ui]
+  slash = True
+  interactive = False
+  [defaults]
+  backout = -d "0 0"
+  commit = -d "0 0"
+  tag = -d "0 0"
+  [extensions]
+  graphlog=
+  rebase=
+  mq=
+  
+  [phases]
+  publish=False
+  
+  [alias]
+  tglog  = log -G --template "{rev}: '{desc}' {branches}\n"
+  theads = heads --template "{rev}: '{desc}' {branches}\n"
+  [ui]
+  logtemplate={rev} {desc} {phase}\n
+
+
+  $ hg init c4
+  $ cd c4
+
+  $ echo a > a
+  $ hg ci -Am A
+  adding a
+  $ echo b > b
+  $ hg ci -Am B
+  adding b
+  $ hg up 0
+  0 files updated, 0 files merged, 1 files removed, 0 files unresolved
+  $ echo c > c
+  $ hg ci -Am C
+  adding c
+  created new head
+  $ hg up 1
+  1 files updated, 0 files merged, 1 files removed, 0 files unresolved
+  $ hg merge
+  1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  (branch merge, don't forget to commit)
+  $ hg ci -m d
+  $ hg up 2
+  0 files updated, 0 files merged, 1 files removed, 0 files unresolved
+  $ echo e > e
+  $ hg ci -Am E
+  adding e
+  created new head
+  $ hg merge 3
+  1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  (branch merge, don't forget to commit)
+  $ hg ci -m F
+  $ hg up 3
+  0 files updated, 0 files merged, 1 files removed, 0 files unresolved
+  $ echo g > g
+  $ hg ci -Am G
+  adding g
+  created new head
+  $ echo h > h
+  $ hg ci -Am H
+  adding h
+  $ hg up 5
+  1 files updated, 0 files merged, 2 files removed, 0 files unresolved
+  $ echo i > i
+  $ hg ci -Am I
+  adding i
+
+Turn most changeset public
+
+  $ hg ph -p 7
+
+  $ hg heads
+  8 I draft
+  7 H public
+  $ hg log -G
+  @  8 I draft
+  |
+  | o  7 H public
+  | |
+  | o  6 G public
+  | |
+  o |  5 F draft
+  |\|
+  o |  4 E draft
+  | |
+  | o  3 d public
+  |/|
+  o |  2 C public
+  | |
+  | o  1 B public
+  |/
+  o  0 A public
+  
+
+  $ hg rebase --dest 7 --source 5
+  saved backup bundle to $TESTTMP/a3/c4/.hg/strip-backup/*-backup.hg (glob)