diff --git a/hgext/rebase.py b/hgext/rebase.py
--- a/hgext/rebase.py
+++ b/hgext/rebase.py
@@ -326,11 +326,11 @@ class rebaseruntime(object):
             self.ui.status(_('nothing to rebase\n'))
             return _nothingtorebase()
 
-        root = min(rebaseset)
-        if not self.keepf and not self.repo[root].mutable():
-            raise error.Abort(_("can't rebase public changeset %s")
-                             % self.repo[root],
-                             hint=_("see 'hg help phases' for details"))
+        for root in self.repo.set('roots(%ld)', rebaseset):
+            if not self.keepf and not root.mutable():
+                raise error.Abort(_("can't rebase public changeset %s")
+                                  % root,
+                                  hint=_("see 'hg help phases' for details"))
 
         (self.originalwd, self.target, self.state) = result
         if self.collapsef:
diff --git a/tests/test-rebase-scenario-global.t b/tests/test-rebase-scenario-global.t
--- a/tests/test-rebase-scenario-global.t
+++ b/tests/test-rebase-scenario-global.t
@@ -329,6 +329,10 @@ Check rebasing public changeset
   abort: can't rebase public changeset e1c4361dd923
   (see 'hg help phases' for details)
   [255]
+  $ hg rebase -d 5 -r '1 + (6::)'
+  abort: can't rebase public changeset e1c4361dd923
+  (see 'hg help phases' for details)
+  [255]
 
   $ hg rebase -d 5 -b 6 --keep
   rebasing 6:e1c4361dd923 "C"