diff --git a/hgext/rebase.py b/hgext/rebase.py
--- a/hgext/rebase.py
+++ b/hgext/rebase.py
@@ -1087,9 +1087,35 @@
     if len(bases) > 1:
         bases.difference_update(ancestor(rev, d) for d in set(dests))
 
-    # Only pick the merge base if we have a unique candidate
-    if len(bases) == 1:
-        base = next(iter(bases))
+    # If there are still multiple candidates, prefer obsoleted ones with
+    # successor in destination. Otherwise we might re-introduce unwanted
+    # obsoleted changes. For example,
+    #
+    #     C      # rebase -r A+B+C -d D
+    #    /|      # Suppose A has content "+A", B has "+B", D has "+D".
+    #   A B   D  # replace: A is replaced by D
+    #
+    # B gets moved on top of D, A gets skipped, C gets moved on top of B':
+    #
+    #         C' # When choosing merge base for C, A and B are candidates.
+    #         |  # If we choose B, the difference between C and B are "+A",
+    #     C   B' # and C' will have the content "+A", which is suboptimal
+    #    /|   |  # because it re-introduces obsoleted content. If we choose
+    #   A B   D  # A as merge base, it works as expected - C' may be empty.
+    if len(bases) > 1:
+        bases = set(r for r in bases if any(ancestor(dest, s) == s
+                                            for s in successorrevs(repo, r)))
+
+    # Pick one candidate. Even if there is no unique candidate, picking one is
+    # better than letting the merge code to decide.
+    if len(bases) >= 1:
+        if len(bases) > 1:
+            # This is worth a warning since the merge could be suboptimal.
+            # See the test case introduced by this changeset for an example.
+            repo.ui.warn(_('warning: cannot decide a unique merge base for '
+                           '%d:%s, merge result may be suboptimal\n')
+                         % (rev, short(cl.node(rev))))
+        base = max(bases)
 
     return newps[0], newps[1], base
 
diff --git a/tests/test-rebase-obsolete.t b/tests/test-rebase-obsolete.t
--- a/tests/test-rebase-obsolete.t
+++ b/tests/test-rebase-obsolete.t
@@ -1069,9 +1069,8 @@
   rebasing 2:b18e25de2cf5 "D" (D)
   note: not rebasing 3:7fb047a69f22 "E" (E), already in destination as 1:112478962961 "B"
   rebasing 5:66f1a38021c9 "F" (F tip)
+  note: rebase of 5:66f1a38021c9 created no changes to commit
   $ hg log -G
-  o  7:9ed45af61fa0 F
-  |
   o  6:8f47515dda15 D
   |
   | x    5:66f1a38021c9 F
@@ -1105,12 +1104,11 @@
   note: not rebasing 2:b18e25de2cf5 "D" (D), already in destination as 1:112478962961 "B"
   rebasing 3:7fb047a69f22 "E" (E)
   rebasing 5:66f1a38021c9 "F" (F tip)
+  note: rebase of 5:66f1a38021c9 created no changes to commit
 
-Rebased F should have one parent, just like in the test case above
+F should disappear, just like in the test case above
 
   $ hg log -G
-  o  7:502540f44880 F
-  |
   o  6:533690786a86 E
   |
   | x    5:66f1a38021c9 F
@@ -1127,6 +1125,77 @@
   
   $ cd ..
 
+Rebase merge where both parents have successors in destination
+
+  $ hg init p12-succ-in-dest
+  $ cd p12-succ-in-dest
+  $ hg debugdrawdag <<'EOS'
+  >   E   F
+  >  /|  /|  # replace: A -> C
+  > A B C D  # replace: B -> D
+  > EOS
+  $ hg rebase -r ::E -d F
+  note: not rebasing 0:426bada5c675 "A" (A), already in destination as 2:96cc3511f894 "C"
+  note: not rebasing 1:fc2b737bb2e5 "B" (B), already in destination as 3:058c1e1fb10a "D"
+  rebasing 4:d6e82823588a "E" (E)
+  warning: cannot decide a unique merge base for 4:d6e82823588a, merge result may be suboptimal
+  $ hg log -Gp -T '{rev}:{node|short} {desc|firstline}\n'
+  o  6:d0827eab33f0 E
+  |  diff -r e0c929a964ce -r d0827eab33f0 A
+  |  --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+  |  +++ b/A	Thu Jan 01 00:00:00 1970 +0000
+  |  @@ -0,0 +1,1 @@
+  |  +A
+  |  \ No newline at end of file
+  |
+  o    5:e0c929a964ce F
+  |\   diff -r 058c1e1fb10a -r e0c929a964ce C
+  | |  --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+  | |  +++ b/C	Thu Jan 01 00:00:00 1970 +0000
+  | |  @@ -0,0 +1,1 @@
+  | |  +C
+  | |  \ No newline at end of file
+  | |
+  | | x    4:d6e82823588a E
+  | | |\   diff -r 426bada5c675 -r d6e82823588a B
+  | | | |  --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+  | | | |  +++ b/B	Thu Jan 01 00:00:00 1970 +0000
+  | | | |  @@ -0,0 +1,1 @@
+  | | | |  +B
+  | | | |  \ No newline at end of file
+  | | | |
+  | o | |  3:058c1e1fb10a D
+  |  / /   diff -r 000000000000 -r 058c1e1fb10a D
+  | | |    --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+  | | |    +++ b/D	Thu Jan 01 00:00:00 1970 +0000
+  | | |    @@ -0,0 +1,1 @@
+  | | |    +D
+  | | |    \ No newline at end of file
+  | | |
+  o | |  2:96cc3511f894 C
+   / /   diff -r 000000000000 -r 96cc3511f894 C
+  | |    --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+  | |    +++ b/C	Thu Jan 01 00:00:00 1970 +0000
+  | |    @@ -0,0 +1,1 @@
+  | |    +C
+  | |    \ No newline at end of file
+  | |
+  | x  1:fc2b737bb2e5 B
+  |    diff -r 000000000000 -r fc2b737bb2e5 B
+  |    --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+  |    +++ b/B	Thu Jan 01 00:00:00 1970 +0000
+  |    @@ -0,0 +1,1 @@
+  |    +B
+  |    \ No newline at end of file
+  |
+  x  0:426bada5c675 A
+     diff -r 000000000000 -r 426bada5c675 A
+     --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+     +++ b/A	Thu Jan 01 00:00:00 1970 +0000
+     @@ -0,0 +1,1 @@
+     +A
+     \ No newline at end of file
+  
 Test that bookmark is moved and working dir is updated when all changesets have
 equivalents in destination
   $ hg init rbsrepo && cd rbsrepo